[백준] 1914번: 하노이 탑 - Kotlin[코틀린]

문제

 

1914번: 하노이 탑

 

---

풀이

 

 하노이의 탑 문제는 큰 부분을 작은 부분으로 나누어 해결하는 재귀적 접근으로 해결할 수 있다.

 원판을 모두 목적지로 옮기기 위해서는 먼저 가장 큰 원판을 목적지로 옮겨야한다. 따라서 나머지 원판들을 목적지가 아닌 곳으로 옮긴다. 나머지 원판들을 모두 옮기고 나면 가장 큰 원판을 목적지로 옮기고 그 후에 나머지 원판들을 목적지로 옮기면 된다.

 위의 과정은 재귀를 이용해 해결할 수 있는데, 두번째로 큰 원판 또한 목적지로 옮기기위해 나머지 원판들을 목적지가 아닌 곳으로 옮기고, 두번째로 큰 원판을 목적지로 옮겨야하기 때문이다.

 

 다만, 이 문제에서는 입력 범위가 크기때문에 재귀적 접근에서 메모리 초과가 발생할 수 있다. 따라서 문제에서 입력이 20보다 큰 경우에는 재귀로 풀이하지 않고 이동 횟수만 출력하도록 했다. 하노이 탑의 이동 횟수를 구하는 공식은 $2^{n}-1$인데 Int의 범위를 넘을 수 있기 때문에 BigInteger를 사용하여 이동 횟수를 구하면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val sb = StringBuilder()

    fun hanoi(num: Int, start: Int, sub: Int, to: Int) {
        if (num == 0) return
        hanoi(num - 1, start, to, sub) // 가장 큰 원판을 목적지로 이동하는 과정
        sb.append("$start $to\n") // 이동한 원판의 경로를 기록
        hanoi(num - 1, sub, start, to) // 나머지 원판들을 목적지로 이동하는 과정
    }

    bw.append("${2.toBigInteger().pow(num).subtract(1.toBigInteger())}\n")
    if(num<=20) { hanoi(num, 1, 2, 3) }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}