<프로그래머스> 하노이의 탑(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/12946

테스트 케이스

학교에서나 혼자 문제 풀 때 많이 봤었던 하노이 탑 문제였다.

그 때는 참 순서가 이해가 잘 이해가 안 갔었는데... 지금 와서 보니까 좀 쉽다는 생각은 들더라

 

하노이탑에서 가장 중요한 거는 n개 중에 n-1개를 먼저 보내려는 기둥말고 다른 기둥에 옮겼다가 남아 있던 1개를 옮긴 후에 보내려는 기둥에 옮기는 거다.

위의 말대로 그냥 코드를 작성했다.

재귀로 구현을 했고 n이 1일 때는 그냥 원하는 곳에 옮기면 되기 때문에 탈출조건이 되었다.

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    private var answer = arrayOf<IntArray>()
    fun solution(n: Int): Array<IntArray> {
        solve(n, 1, 3, 2)
        return answer
    }

    private fun solve(num: Int, from: Int, to: Int, temp: Int) {
        if (num == 1) {
            answer += intArrayOf(from, to)
            return
        }

        solve(num - 1, from, temp, to) // num - 1개를 다른 곳에 옮기기
        answer += intArrayOf(from, to) // 남은 하나 옮기기
        solve(num - 1, temp, to, from) // num - 1개 옮기기
    }
}