[BOJ][KOTLIN] 11729 하노이 탑 이동 순서

풀이

1. 기둥 세개를 시작, 중간, 끝 위치로 설정한다.
2. 3개의 탑을 옮길때 1, 2 를 하나의 묶음으로 생각하고 N = 2 와 동일한 이동으로 생각한다.
3. 2번 과정을 통해서 아래와 같은 알고리즘 규칙을 도출 한다.

• hanoi(N - 1, start, mid, end) // N - 1 개의 원탑을 끝 기둥을 이용하여 중간 기둥으로 이동
• hanoi(1, start, end, mid) // 1개의 원탑을 끝 기둥으로 이동
• hanoi(N - 1, mid, end, start) // 첫번째에서 이동된 N - 1 원탑을 중간 기둥에서 시작 기둥을 이용하여 끝 기둥으로 이동

import java.io.*

var count = 0
var result = mutableListOf<String>()

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val N = br.readLine().toInt()
    hanoi(N, 1, 3, 2)
    bw.write("${count}\n")

    for (res in result) {
        bw.write("${res}\n")
    }

    bw.flush()
    bw.close()
    br.close()
}

private fun hanoi(N: Int, start: Int, end: Int, mid: Int) {
    if (N == 1) {
        count++
        result.add("$start $end")
    } else {
        hanoi(N - 1, start, mid, end)
        hanoi(1, start, end, mid)
        hanoi(N - 1, mid, end, start)
    }
}