[백준]11729. 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

---

풀이

이 문제도 옮긴 횟수 K의 규칙성은 알겠는데, 이동하는 것을 출력하는 부분에서 막혀 한참 고민하다 블로그를 찾아보았다.
저번에 별찍기 문제에서도 도움을 받은 분이었는데, 하노이 탑이 왜 재귀 함수를 사용해서 풀어야 하는 문제인지 단계별로 그림과 함께 설명해주셔서 이해하기 쉬웠다.(https://mgyo.tistory.com/185)

'하노이의 탑' 이해하기 (feat. 재귀 함수)

하노이 탑이 재귀함수인 이유는 맨 마지막 막대에 N개만큼의 탑을 쌓기 위해서는, 마지막 N번째 원반을 제외한 N-1개의 원반이 마지막 막대를 제외한 막대에 차례대로 쌓여야 하기 때문이다. 그리고 N번째 원반이 마지막 막대로 이동한 후, 1부터 N-1개의 원반이 다시 마지막 막대에 순서대로 쌓여야 한다. 즉 Hanoi(N)이 이루어지려면 Hanoi(N-1)이 두 번 이뤄져야 한다. 

출처: 밤샘공부님 블로그 (https://study-all-night.tistory.com/m/6)

Hanoi 라는 재귀함수를 어떻게 작성하면 좋을지 고민해보면, 아래와 같이 적을 수 있다. N==1일 때(원반이 1개일 때)는 원반을 그냥 1번에서 3번 막대로 이동시키면 되므로 이동 횟수는 1회이다. 이동했음을 나타내는 명령문을 프린트해주면 된다.
여기서 중요한 것은 N-1개의 원반이 처음에는 시작점에서 종료지점을 거쳐 중간지점으로 최종 이동하지만, N번째 원반이 마지막 막대로 이동한 이후에는 현재 위치해있는 중간지점에서 시작점을 거쳐 종료지점으로 이동한다는 것이다.   

출처: mgyo님 블로그 (https://mgyo.tistory.com/185)

그리고 이동 횟수 K도 재귀의 원리로 생각하면 간단하다. 가령 Hanoi(2)는 Hanoi(1) * 2(이동 전 후에 재귀) + 1(N번째 원반 이동) = 3이고, Hanoi(3)은 Hanoi(2) * 2 + 1 = 7 이고 규칙성을 찾아보면 2ⁿ-1의 규칙성을 가지고 있음을 알 수 있다.

이 재귀함수를 코드로 적으면 다음과 같다.

# 11729 하노이탑 924ms
# https://mgyo.tistory.com/185 참고
# Hanoi(n)은 H(n-1) * 2 (마지막 원반 옮기기 전, 후) + 1(마지막 원반 옮기기) 인 재귀식이다!

MSG_FORMAT = '{} {}'
def Move(start, end):
    print(MSG_FORMAT.format(start, end))

def Hanoi(N, start, end, sub):
    if N == 1:
        Move(start, end)
        return
    else:
        Hanoi(N-1, start, sub, end)
        Move(start, end)
        Hanoi(N-1, sub, end, start)

N = int(input())
print(2 ** N - 1)
Hanoi(N, 1, 3, 2)