백준 11729번: 하노이 탑 이동 순서

문제: https://www.acmicpc.net/problem/11729

문제 풀이

재귀

n개의 하노이 탑을 이동하려면 다음 단계를 거침

1. n - 1개의 하노이 탑을 빈칸으로 옮김
2. 크기가 n인 원판을 목적지로 옮김
3. 빈칸으로 옮겨놓았던 n - 1개의 하노이 탑을 목적지로 옮김

이에 따라 재귀 함수로 구현하면 재귀 함수가 호출되어 원판을 옮길 때의 횟수를 세고 옮기는 과정을 출력하면 정답

풀이 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

반경이 서로 다른 n개의 원판이 반경이 큰 순서대로 쌓여 있고, 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 하기 때문에 가장 큰 원판이 세 번째 장대의 가장 아래에 들어가려면 두 번째 장대에 n - 1개의 원판이 쌓여 있어야 세 번째 장대에 가장 큰 원판을 옮길 수 있다.

즉, 하노이 탑을 옮기는 순서는 다음과 같게 된다.

1. n - 1개의 하노이 탑을 빈칸으로 옮김
2. 크기가 n인 원판을 목적지로 옮김
3. 빈칸으로 옮겨놓았던 n - 1개의 하노이 탑을 목적지로 옮김

이에 따라 재귀 함수 hanoi(level, start, empty, end)를 정의한다. level은 옮기는 하노이 탑의 원판 수이고, start는 옮겨야 하는 하노이 탑이 있는 위치, empty는 level - 1개의 원판으로 이루어진 하노이 탑을 옮길 위치, end는 하노이 탑을 최종적으로 옮겨야 하는 위치이다.

따라서 순서에 맞게 n - 1개의 하노이 탑을 빈칸으로 옮기도록 hanoi(level - 1, start, end, empty)를 호출한다. 그 이후에 가장 큰 원판을 목적지로 옮기는 것이므로 옮길 때의 출력을 저장하기 위해 StringBuilder에 start와 end를 넣는다. 마지막으로 빈칸으로 옮겨놓았던 n - 1개의 하노이 탑을 옮겨놓은 가장 큰 원판위로 올리기 위해 hanoi(level - 1, empty, start, end)를 호출한다.

원판을 옮기는 횟수는 함수를 한 번 호출하면 원판을 한 번 옮기므로 함수가 실행될 때의 횟수를 세면 된다. 따라서 answer를 전역 변수로 정의하고 0으로 초기화 한 후에 함수가 실행될 때 값을 1씩 증가 시키면 된다.

이에 따라 answer를 출력하고 StringBuilder에 저장된 문자열들을 출력하면 정답이 된다.

소스 코드

var answer = 0
val sb = StringBuilder()

fun main(){
    val br = System.`in`.bufferedReader()
    val N = br.readLine().toInt()
    hanoi(N, 1, 2, 3)
    println(answer)
    print(sb)
}

fun hanoi(level: Int, start: Int, empty: Int, end: Int){
    if(level == 0){
        return
    }
    answer++
    //목적지에 따라 현재 옮겨야 되는것보다 작은거를 재귀로 불러서 옆 칸으로 옮김
    hanoi(level - 1, start, end, empty)
    //현재 옮겨야 하는 가장 큰거를 옮겨야 하는 칸으로 옮김
    sb.append("$start $end\n")
    //처음에 옮겨놨던 작은거를 현재 칸으로 옮기는 재귀 호출
    hanoi(level - 1, empty, start, end)
}