Swift) 백준 11729번 (하노이 탑)

요구능력 : 재귀함수를 응용할 수 있느냐

 

코드설명 : 

우선, 몇번 왔다갔다했는지 봐야되는데 그럼 count같은 변수를 넣어서 세봤자 소용이 없다.

규칙을 찾아보면 (2의 n승) -1을 하면 이동횟수가 나오게 된다.

hanoi 함수의 인자 n은 우리가 입력받는 수, start는 첫번째 장대, mid는 두번째 장대, end는 세번째 장대이다.

첫번째 하노이 함수는 n-1 개의 원판을 2번째 장대로 옮기는것

두번째 하노이 함수는 남은 1개의 맨 마지막 원판(n이 3이면 3짜리원판)을 3번째 장대로 옮기는것

세번째 하노이 함수는 2번째 장대에 놓은 n-1개의 원판을 3번째 장대로 옮기는것

자세한건 저도 완벽하게 이해 못했기 때문에 디버깅보고 재귀함수라도 이해하고 가세용..(악필 이해 좀 해주세요ㅎ..)

 

후기 : 난 매우매우매우 어려웠다.

개인적으로 처음 접해보는 유형(?)이었기 때문에....

재귀로 저렇게 만들건 생각도 못했지... 그래서 구글링으로 찾아보고 유튭검색해보면서 이해했다..

이건, 솔직히 답보고 이해하고 혼자 디버깅 할 줄 알게되서 어느정도 재귀함수를 이해했다는 것만으로 이득이다.

다른 알고리즘을 보면 아! 이런식으로 접근해서 이렇게 풀면 되겠구나 라는 생각이 들정도로 이해하고 넘어가는 편인데

이 알고리즘을 혼자서 어떻게 짤까? 라는 생각밖에 안든다.

다른사람들 설명을 봐도 그냥 맨윗부분은 n - 1 만큼을 2번째 원판으로 옮기는거에요.

이런식으로 자세한 설명없이 포괄적인 말 뿐인데, 이건 한번 들은사람이면 다 할 수 있는말..

import Foundation
let n = Int(readLine()!)!
print("\(pow(2, n) - 1)")
hanoi(n, 1, 2, 3)


func hanoi(_ n: Int, _ start: Int, _ mid: Int, _ end: Int) {
    if n == 1 {
        print("\(start) \(end)")
        return
    }
    hanoi(n-1, start, end, mid)
    hanoi(1, start, mid, end)
    hanoi(n-1, mid, start, end)
}

---

디버깅