[Python] Baekjoon11729: 하노이 탑 이동 순서

하노이 탑 이동 순서

1 초

256 MB

49339

24422

18965

49.144%

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

풀이

이 문제를 풀었던게 엊그제 같은데... 재귀 단원을 현재 처음 배운다면 충격적인 문제가 아닐 수 없습니다.

N = int(input())
lst = []
def hanoi(x,y,z,depth): # x: 출발, y: 경유, z: 도착
    if depth == 1:
        return [[x,z]]
    return hanoi(x,z,y,depth - 1) + [[x,z]] + hanoi(y,x,z,depth - 1)
print(2**N-1)
for i in hanoi(1,2,3,N):
    print(*i)

N번째 하노이탑은 1번에서 출발해 2번을 경유하고 3번에서 도착합니다.

N-1번째 하노이탑 또한  1번에서 출발해 2번을 경유하고 3번에서 도착하는데 N번째 하노이탑의 입장에서는 N-1번째 하노이탑을 1번에서 출발해 2번으로 옮기고 1번에서 3번으로 가장 큰 판을 옮긴다음 N-1번째 하노이탑을 2번째에서 3번째로 옮기는 작업과 동일합니다.

[N] 하노이탑 쌓는 법 = [N-1]번째 하노이탑을 (1에서 2로 옮김) + 1에서 3으로 가장 큰 판 옮기기 + [N-1]번째 하노이탑을 2에서 3으로 옮기기

이를 응용해 매개변수의 이동만으로 하노이탑을 완성할 수 있습니다.

hanoi(x,y,z,depth) # depth = N번째 하노이탑

hanoi(x,z,y,depth - 1) + [[x,z]] + hanoi(y,x,z,depth - 1)
# N-1번째 하노이탑이 1에서 2로 이동 + 1에서 3이동 + N-1번째 하노이탑이 2에서 3 이동