TIL 코딩공장

백준 파이썬 공부 2025.01.01
1914번 하노이 탑 (골드 5)

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

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 
단, 이동 횟수는 최소가 되어야 한다.

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

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

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

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 
두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 
이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. 
N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

4. 문제 풀이
하노이 탑의 풀이법은 재귀이다.
일단은 가장 큰 원판을 제외한 모든 원판을 한 덩어리로 생각하자.
그리고 원판이 위치한 장대을 start, 도착지 장대를 end, 보조 장대를 sub라 할 때, 
모든 원판을 마지막 원판에 옮기는 방법은
1) 덩어리 원판을 start에서 sub 장대로 옮기고
2) 가장 큰 원판을 start에서 end 장대로 옮기고,
3) 덩어리 원판을 sub에서 end 장대로 옮기는 것이다.

이를 재귀 함수로 만들어 돌리면 된다.

>>코드

def hanoi(n):
    if n == 1:
        return 1
    return 2 * hanoi(n - 1) + 1 # 덩어리 원판 2번 옮기기 + 큰 원판 한번 옮기기

def print_hanoi(start, end, sub, n):
    if n == 0:
        return
    print_hanoi(start, sub, end, n - 1)  # start >> sub로 덩어리 원판 옮기기
    print(start, end)  # start >> end로 가장 큰 원판 이동 출력
    print_hanoi(sub, end, start, n - 1)  # sub >> end로 덩어리 원판 옮기기

n = int(input())
print(hanoi(n))
if n <= 20:
    print_hanoi(1, 3, 2, n)

5. 문제 링크
https://www.acmicpc.net/problem/1914