문제
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
풀이
하노이의 탑 문제는 큰 부분을 작은 부분으로 나누어 해결하는 재귀적 접근으로 해결할 수 있다.
원판을 모두 목적지로 옮기기 위해서는 먼저 가장 큰 원판을 목적지로 옮겨야한다. 따라서 나머지 원판들을 목적지가 아닌 곳으로 옮긴다. 모두 옮기고 나면 가장 큰 원판을 목적지로 옮기고 그 후에 나머지 원판들을 목적지로 옮기면 된다.
위의 과정은 재귀를 이용해 해결할 수 있는데, 두번째로 큰 원판 또한 목적지로 옮기기위해 나머지 원판들을 목적지가 아닌 곳으로 옮기고 난 뒤에 두번째로 큰 원판을 목적지로 옮겨야하기 때문이다.
코드
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()
}
'알고리즘 > Baekjoon' 카테고리의 다른 글
[백준] 2630번: 색종이 만들기 - Kotlin[코틀린] (0) | 2024.02.05 |
---|---|
[백준] 2503번: 숫자 야구 - Kotlin[코틀린] (0) | 2024.01.29 |
[백준] 11000번: 강의실 배정 - Kotlin[코틀린] (0) | 2024.01.22 |
[백준] 5567번: 결혼식 - Kotlin[코틀린] (0) | 2024.01.21 |
[백준] 24511번: queuestack - Kotlin[코틀린] (0) | 2024.01.18 |