[백준/BOJ] 11729번: 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

문제

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

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

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

아래 그림은 원판이 5개인 경우의 예시이다.

해설

그림을 보며 이해해보자.

이와 같은 하노이 탑이 있다.

A에 가장 큰 원 한개만 남겨두기 위해 n-1개의 원반을 B로 옮긴다.

A에 가장 큰 원만 남아있으므로 이를 C로 옮긴다.

B에 있는 n-1개의 원판을 C로 옮긴다.

이를 보면 원반 n개를 이동하는 것은 원반 n-1개로 이동하는 문제로 세분화된다.

따라서 n=1이 될 때까지 세분화를 시키면 된다.

 

코드를 보면서 이해해보자.

소스 코드

import java.lang.Math.pow
import java.lang.StringBuilder

val sb = StringBuilder()
var cnt = 0
fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    var cnt = pow(2.0, n.toDouble()).toInt() - 1
    Hanoi(n, 1, 2, 3)
    println(cnt)
    println(sb.toString())
}

fun Hanoi(n: Int, start: Int, to: Int, arrive: Int) {
    // 원반이 한개 남았을 때
    if(n == 1) {
        sb.append("$start $arrive\n")
        cnt++
        return
    }
    // num-1개의 원반을 1에서 2로 이동시킨다.
    Hanoi(n-1, start, arrive, to)
    // 1에 한개의 원반이 남았으므로 C로 옮긴다.(이를 출력)
    sb.append("$start $arrive\n")
    // 2에 있는 n-1개의 원반을 3으로 옮긴다.
    Hanoi(n-1, to, start, arrive)
}