[Python | 11729] 하노이 탑 이동 순서

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

---

문제 설명

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

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

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

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

 

📌 시간 제한: 1초

---

입력

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

---

출력

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

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

---

문제 접근

하노이 탑 문제를 처음 봤을 때 규칙만 잘 이해하면 반복적인 패턴이 보일 것 같았고, 원반을 옮기는 순서 자체보다는 어떤 순서로 옮겨야 최소 횟수로 끝낼 수 있을지가 핵심이라고 느꼈다.

처음엔 작은 원반 개수부터 직접 그려봤다. 2개일 땐 금방 옮길 수 있었고, 3개가 되자 조금 더 복잡해졌지만 결국 ‘가장 큰 원반을 마지막에 옮기기 위해, 그 위에 있는 것들을 잠깐 옮겨야 한다’는 공통 구조가 반복된다는 걸 알게 됐다.

→ 결국, n개의 원반을 옮기려면

1. n-1개를 다른 기둥으로 옮기고
2. 가장 큰 원반을 목적지로 옮긴 다음
3. n-1개를 다시 그 위로 옮기는 구조가 된다.

이걸 계속 반복해서 쪼개다 보면, 마지막엔 원반이 1개일 때까지 도달한다. 그 시점부터는 더 쪼갤 필요 없이 바로 옮기면 되기 때문에, 그게 재귀의 기저 조건이 됐다. 그리고 옮기는 횟수가 T(n) = 2×T(n-1) + 1이라는 점화식으로 이어진다는 것도 쉽게 확인할 수 있었다.

이 점화식을 풀면 T(n) = 2^n - 1이라는 일반항이 나오고, 여기서 각 호출마다 출력이 한 번씩 포함된다는 점을 고려하면, 전체 알고리즘의 시간복잡도는 O(2^n)이 된다.

위 그림처럼, 큰 원반을 옮기기 위해 그 위의 n-1개를 잠시 옮겼다가 다시 되돌리는 흐름이 반복된다.

---

구현

재귀함수를 구성할 때도 자연스럽게 이 흐름대로 짰다. hanoi(n, start, via, end)라는 함수 하나로, 위에 정리한 3단계를 그대로 재귀 호출로 표현했다. 문제에서 요구한 이동 횟수는 2^n - 1이라는 공식도 간단한 규칙으로 유도할 수 있었다.

def hanoi(n, a, b, c):
    if n == 1:
        print(a, c)
    else:
        hanoi(n-1, a, c, b)
        print(a, c)
        hanoi(n-1, b, a, c)

n = int(input())
print(2**n - 1)  # 이동 횟수는 항상 2^n - 1
hanoi(n, 1, 2, 3)

 

 

Reference: 위키독스, "하노이 탑", https://wikidocs.net/166437