백준 - 하노이 탑 이동 순서 - 11729 - swift

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

11729번: 하노이 탑 이동 순서

 

 

문제는 재귀 유형이다. 

 

우선 풀이에 앞서 정말 감격스럽다. 

코딩테스트 공부한지 1년만에 도움없이 혼자서 이해하고 풀었다.

그전까지 매번 하노이탑 볼 때 마다 이걸 어떻게 푸는건지 감도 오지 않았다. 

심지어 예전에 풀이를 봤을때도 이해가 안갔었다. 

하지만,... 1시간동안 고민 끝에 풀었다!ㅠㅠ 

 

---

 

처음에는 완전탐색으로 접근했다가, 

계속 이동하는 걸 그려보면서 다음과 같은 패턴을 찾을 수 있었다. 

하노이탑 특성상, 가장 무거운 값이 x쪽으로 가고자 한다면, x에는 아무것도 꽂혀 있어서는 안된다.

또한, 가장 밑에 값 ( y ) 이 x쪽으로가고자 한다면,

남은 위치에 y+1이 이동해야한다.

그렇다면 마찬가지로 y+2값도 그 외 위치로 이동해야한다. 

마찬가지로.. y+3.... 

.....

 

 

3개 원판만 예로 들어보자

즉 1,2,3이 먼저 1번 고리에 꽂혀있는데, 결과적으로 3번이 3번 고리에 꽂혀야한다.

그러기 위해서는 1,2번이 2번고리에 꽂혀 있어야한다. 

 

이걸 좀더 재귀 스럽게 표현해보면...  아래 그림처럼 표현할 수 있다. 

( 아래 그림은 위에서 아래로 읽어야 한다.  )

 

그리고 이제 이어서 더 설명해보면,

노란색의 결과 1부터 보면 된다.

( 이번엔 아래에서 위로 읽어야한다. ) 

 

 

 

결과 6번을 보면, 어디서 많이 본 것 같다. 

맞다!  처음에 했던 방식과 같다. 

처음에는 2번이 1번고리에서 2번고리로 이동하는 거였지만,

이제는 결과6번 부터는 2번은 2번고리에서 3번고리로 이동해야한다.

마찬가지로, 2번은 빼놓고 생각하면, 

이제 1번이 2번고리에서 1번 고리로 이동해야한다. 

 

 

재귀가 보이시나요?! 

재귀가 총 2번 시작하게 됩니다. 

 

만약, y(무게)를 x1위치에서 x3위치로 옮기려고 한다면,

y+1를 x1위치에서 x2위치로 옮겨야한다. <- 재귀  이 부분이 모두 완료됐다면,

이제 y는 x3위치로 옮길 수 있게 되고, 

이제 다시 y+1를 x2위치에서 x3위치로 옮겨야한다.  <- 재귀 

 

첫번째 재귀가 완료되면 가장 무거운 값이외의 모든 값들이 x2위치에 차곡차곡 쌓여있게 된다.

두번째 재귀가 완료되면 모든 값들이 x3위치에 차곡차곡 쌓여있게 된다.

 

이 재귀함수의 기저사례는 무게가 1인 경우이다.

1인 경우는 어디로든 움직일 수 있다. 1보다 가벼운 무게는 없기 때문이다. 

 

이걸 코드로 적는 다면 다음과 같이 적을 수 있다.

let N = Int(readLine()!)!
var count = 0
var ans = ""

func find(x: Int, cur: Int,  to: Int, empty: Int  ) {
    if x == 1 {
        count += 1
        ans += "\(cur) \(to)\n"
        return
    }
    find(x: x-1, cur: cur, to: empty, empty: to)
    ans += "\(cur) \(to)\n"
    count += 1
    find(x: x-1, cur: empty, to: to, empty: cur)
}

find(x: N, cur: 1, to: 3, empty: 2)
ans.removeLast()
print(count)
print(ans)

 

 

부디 글을 읽는 분들도 이해가 되시길 바랍니다