[백준/파이썬] 1914번: 하노이 탑

문제

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

풀이

• n개의 원판을 1번 원판에서 3번 원판으로 옮기는 최소 횟수 출력
• a탑에서 b탑으로 이동한 이동경로 출력(n이 20 이하인 경우만)

하노이의 탑에서 원판을 옮길 때는 2가지 규칙이 있습니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

이제 위 규칙을 준수하면서 1번에 있는 원판들을 3번으로 이동시켜야 합니다.

그런데 막상 옮기려고 점화식을 작성하려고 보면 어떻게 옮겨야할지 막막합니다..

점화식을 만들기 위해 원판이 2개일 경우를 예로 들어 확인해보겠습니다.

초기 상태의 하노이의 탑입니다.

이를 3번으로 모두 이동시키기 위해선 위에 있는 작은 원판을 먼저 2번으로 이동시켜 줍니다. [1,2]

그리고 1번에 있는 가장 큰 원판을 3번으로 이동시켜 줍니다. [1,3]

마지막으로 2번에 있던 원판을 3번으로 이동시켜 줍니다. [2,3]

이거만 보면 이해가 가지 않을 수 있습니다.
때문에 원판을 3개로 바꾸어서 확인해보겠습니다.

1. 1번 원판을 3번 탑으로 이동 [1,3]
2. 2번 원판을 2번 탑으로 이동 [1,2]
3. 1번 원판을 2번 탑으로 이동 [3,2]
4. 3번 원판을 3번 탑으로 이동 [1,3]
5. 1번 원판을 1번 탑으로 이동 [2,1]
6. 2번 원판을 3번 탑으로 이동 [2,3]
7. 1번 원판을 3번 탑으로 이동 [1,3]

여기서 잘 보시면 규칙이 보이기 시작합니다.
우선 1번 탑에 있던 원판들(가장 큰 원판 제외)을 모두 2번 탑으로 이동시킨 후, 가장 큰 원판을 3번 탑으로 이동시킵니다.
그 후에, 2번탑에 있는 원판들을 3번 탑으로 이동시키면 종료가 됩니다.

이를 n개로 치환하여 식을 세워보면
1. 1번 탑에 있는 n-1개의 원판을 3번 탑에 경유하여 2번 탑으로 이동
2. 1번 탑에 남아 있는 가장 큰 원판을 3번 탑으로 이동
3. 2번 탑에 있는 n-1개의 원판을 1번 탑에 경유하여 3번 탑으로 이동

위 식을 이용해서 함수를 작성해보겠습니다.

def hanoi(n, dep, via, arr): # 개수, 출발, 경유, 도착
    if n == 1:
        print(dep, arr)
    else:
        hanoi(n-1, dep, arr, via) # n-1개: 1번 -> 3번 -> 2번
        print(dep, arr) # 가장 큰 원판: 1번 -> 3번
        hanoi(n-1, via, dep, arr) # n-1개: 2번 -> 1번 -> 3번

원판의 개수가 1개인 경우)
시작 지점(1번 탑)에서 도착할 탑(3번 탑)으로 바로 이동할 수 있으므로 dep과 arr을 바로 출력해줍니다.

원판의 개수가 2개 이상일 경우)
1. n-1개의 원판을 1번 탑에서 3번 탑을 경유해 2번 탑으로 이동시켜 줍니다.
2. 1번 탑에 있는 가장 큰 원판을 3번 탑에 옮겨 줍니다.(출력)
3. n-1개의 원판을 2번 탑에서 1번 탑을 경유해 3번 탑으로 이동시켜 줍니다.

---

우리는 하노이 탑의 이동 횟수를 먼저 출력해야 합니다.
이동 횟수는 $2^n - 1$이므로 바로 출력해줍니다.
n이 20 이하일 때만 이동 경로를 나타내라고 했으니 조건문까지 달아주면 완성 😋

if __name__ == "__main__":
    n = int(input())
    print(2**n - 1)
    if n <= 20:
        hanoi(n, 1, 2, 3)

코드

import sys
input = sys.stdin.readline

def hanoi(n, dep, via, arr): # 개수, 출발, 경유, 도착
    if n == 1:
        print(dep, arr)
    else:
        hanoi(n-1, dep, arr, via) # n-1개: 1번 -> 3번 -> 2번
        print(dep, arr) # 가장 큰 원판: 1번 -> 3번
        hanoi(n-1, via, dep, arr) # n-1개: 2번 -> 1번 -> 3번

if __name__ == "__main__":
    n = int(input())
    print(2**n - 1) # 이동 횟수
    if n <= 20:
        hanoi(n, 1, 2, 3)