하노이의 탑 - Kotlin

프로그래머스

문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

 

나의 풀이

  이 문제는 분할 정복법을 이용해서 차근차근히 문제를 접근해가면 생각보다 간단한게 해결할 수 있는 문제이다. 분할 정복법이란, 처음에 해결하려고 하는 문제를 크기가 보다 작은 여러 개의 부분 문제로 분할한다. 단, 이 때 크기가 작은 부분 문제에 대한 답으로부터 원래의 문제에 대한 해답을 쉽게 얻을 수 있게 분할할 필요가 있다. DP와 비슷해서 DP와 헷갈리는 사람이 있는데, DP가 성립하기 위한 가장 큰 조건인 '부분 문제가 중복되어야 한다.' 라는 조건은 분할 정복법에는 해당하지 않는다. 

 하노이의 탑 문제는 분할 정복법의 가장 유명한 문제이다. 만약 막대가 삼각형의 형태로 배치되어 있다고 하면, 홀수 번째에는 가장 작은 원판을 시계 방향으로 하나만 이동하고, 짝수 번째에는 제일 작은 원판을 제외한 나머지 원판 중에서 이동할 수 있는 것만을 하나 이동한다.

 

 원판 n 장을 A 에서 B 로 이동하는 문제는 크기가 n - 1 인 두 개의 부분 문제로 구성된 것이라고 생각할 수 있다.

첫번째 문제: n - 1장의 원판을 막대 A 에서 막대 C 로 옮기면 막대 A 에 있던 n 번째 작은 원판 (가장 큰 원판) 을 옮길 수 있 상태가 되므로 그 원판을 A 에서 B 로 옮긴다. 두번째 문제:  n - 1 장의 원판을 막대 C에서 B로 이동한다.

 n-1장의 원판을 옮기기 위해서는 이 방법을 재귀적으로 사용하면 되는데, 여기서 이동하는 n - 1 장의 원판은 다른 어느 원판보다도 작으므로 이동할 때에 막대 A, B, C 의 제일 윗부분에는 어떠한 원판이 있는지를 생각할 필요가 없다. 실제로 여러 개의 원판이 어떻게 이동하는지는 알기 어렵고, 재귀 호출이 반복되므로 이것을 하나하나 체크하기는 힘들지만, 이 알고리즘의 아이디어는 이해하기 쉽고 정당하다는 것을 증명하는 것도 비교적 쉽다. 일반적으로 이와 같은 분할 통치법을 이용한 알고리즘은 그렇지 않은 알고리즘보다 효율이 좋다.

class Solution {
    val answer = ArrayList<IntArray>()
    fun solution(n: Int): Array<IntArray> {
        hanoi(n, 1, 3, 2)
        return answer.toTypedArray()
    }

    fun hanoi(n: Int, start: Int, end: Int, via: Int) {
        if (n == 1) {
            answer.add(intArrayOf(start, end))
            return
        }

        hanoi(n - 1, start, via, end)
        answer.add(intArrayOf(start, end))
        hanoi(n - 1, via, end, start)
    }

}