[Python/파이썬] 백준 11729번 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

 

코드

n = int(input())


def hanoi(n, start, other, dest):
    if n == 1:
        print(start, dest)
        return
    hanoi(n-1, start, dest, other)
    print(start, dest)
    hanoi(n-1, other, start, dest)


print(2**n-1)
hanoi(n, 1, 2, 3)

 

하노이 탑 알고리즘을 알고 있어야 해당 문제를 풀 수 있는데 잘 이해가 잘 안돼서 아래의 유튜브 설명을 참조했다.

https://www.youtube.com/watch?v=aPYE0anPZqI

 

영상을 쉽게 요약해보면 n개의 원반과 3개의 장대(start, other, to)가 있고, 처음에 start 장대에 쌓여있는 n개의 원반을 to로 옮긴다고 할 때 아래의 3단계를 반복하는 것이다.

 

1. start에 있는 원반 중 가장 아래 원반을 제외한 n-1개의 원반을 other로 옮긴다.

2. start에 있던 가장 아래 원반을 to로 옮긴다.

3. other로 옮겨놨던 n-1개의 원반을 to로 모두 옮긴다.

 

처음에는 원반을 한 번에 한 개씩만 옮길 수 있다고 했는데 이게 무슨 얘기인가 하겠지만 n개에서 1개씩 줄이며 해당 로직을 수행하다보면 결국 n-1개가 1개가 되는 순간이 온다. 그렇기에 이 문제는 n을 1씩 줄이며 재귀 호출을 해서 문제를 해결하는 것이다.