<백준> 하노이 탑 이동 순서(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%ED%95%98%EB%85%B8%EC%9D%B4%20%ED%83%91%20%EC%9D%B4%EB%8F%99%20%EC%88%9C%EC%84%9C

[백준]

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

제출 결과

 

저번에 프로그래머스에서도 나왔던 문제였는데 거의 비슷하게 나와서 다시 복습하는 문제였다.

이제는 이 구조가 자연스럽게 손으로 나온다.

n개를 옮기려고 할 때 n-1개를 먼저 다른 기둥에 옮겨놓고 1개를 옮긴다음 다른 기둥에 옮겨놓은 n-1개를 목표 기둥에 옮기는 것..!!

중간에 이동 경로를 저장하려면 n이 1일 때나 n-1개를 다른 기둥에 다 옮기고 나서 그 때 이동을 저장하면 된다.

 

재귀로 하는 거지만 손에 익은 재귀는 그냥 슉슉이다~

물론 마지막에 제출하려고 예제를 테스트하는데 스택오버 에러가 떠서 왜지? 했는데 내가 n이 1일 때, 코드를 실행하고 return으로 재귀를 끊지 않고 그냥 달리게 하니까 계속 쌓였던 거였다...ㅎ

그 부분만 수정하고 제출하니 통과했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

var move = 0
var route = StringBuilder()
fun main() = with(System.`in`.bufferedReader()) {
    val num = readln().toInt()

    solve(num, 1, 3, 2)
    println(move)
    println(route)
}

fun solve(num: Int, from: Int, to: Int, with: Int) {
    if (num == 1) {
        route.append("$from $to\n")
        move++
        return
    }

    solve(num - 1, from, with, to)
    route.append("$from $to\n")
    move++
    solve(num - 1, with, to, from)
}