[백준] 11729번: 하노이 탑 이동 순서 - Kotlin[코틀린]

문제

 

11729번: 하노이 탑 이동 순서

 

---

풀이

 

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

 

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

 

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

 

---

 

코드

 

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

    val num = br.readLine().toInt()
    val sb = StringBuilder()
    var cnt = 0

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

    hanoi(num, 1, 2, 3)

    bw.append("$cnt\n")
    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}