[python] 백준 1914번 - 하노이 탑

아주 유명한 하노이 탑 문제..
시작 기둥에 쌓여있는 n개의 원판 모두를 특정 규칙에 따라서 목표 기둥으로 옮겨야 하는 문제이다.
 
규칙은 다음과 같다
1. 한 번에 한 개의 원판만 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
 
원판의 개수 N이 주어지면 옮긴 횟수, 그리고 그 옮긴 과정들을 출력해야 한다.
 
원판을 옮기는 과정에는 어떤 규칙이 있을까?

 
A를 시작 기둥, B를 임시 기동, C를 목표 기둥이라고 하자.
 
가장 먼저 n == 1인 경우에는 단순히 A에 있는 원판을 C로 옮기면 된다.
 
다음으로는 n == 2인 경우를 보자.
원판 두 개를 옮기려면 다음과 같은 과정을 거쳐야 한다.
 
A -> B
A -> C
B -> C
 
일단 A에 있는 작은 원판을 임시 기둥으로 옮긴다.
그 후, 가장 큰 원판을 목표 기둥으로 옮긴다.
마지막으로 임시 기둥에 있던 원판을 목표 기둥으로 옮기게 되면 문제가 끝난다.
 
n == 3인 경우는 어떨까?
보기 전에 먼저 원판을 한 번에 한 개씩 옮길 수 있다는 조건을 빼고
목표 기둥에 옮기려면 어떻게 해야 할지를 확인해보자.
 
A -> B
A -> C
B -> C
 
일단 A에 있던 가장 큰 원판을 제외한 2개의 원판들을 B로 옮겨야 할 것이다.
그 후, A에 남아있는 가장 큰 원판을 C로 옮겨야 할 것이다.
마지막으로 B에 있던 원판들을 옮기면 문제가 끝난다.
 
그럼 다시 돌아가서 A -> B인 상황을 보자.
A에 있는 2개의 원판을 B로 한 번에 옮겼었다.
그렇다면 2개의 원판을 하나씩 B로 옮기려면 몇 번을 옮겨야 할까?
n == 2일 때에서 본 것처럼 3번을 옮겨야 할 것이다.
 
그리고 A -> C에서는 가장 큰 원판을 C로 한 번 옮겼다.
 
마지막으로 B -> C인 상황을 보자.
B에 놓았던 2개의 원판들을 다시 C로 옮겨야 한다.
위에서와 마찬가지로 2개를 하나씩 다른 기둥에 옮기려면 총 3번을 옮겨야 한다.
 
n == 3인 경우를 정리하면 다음과 같다.
 
A -> B : A -> C, A -> B, C -> B    3번
A -> C : 가장 큰 원판을 옮기는 행동.    1번
B -> C : B -> A, B-> C, A -> C    3번
 
총 7번이 소요가 된다.
 
원판의 개수에 따라서 옮긴 횟수는 다음과 같이 정리할 수 있다.
 
n개의 원판을 옮기는 데 필요한 횟수를 f(n)이라고 해보자.
먼저 가장 큰 원판을 옮기는 경우 1번이 무조건 들어갈 것이다.
그리고 그 전후로 원판들을 옮기는 경우는 n-1개의 원판들을 옮기는 행동이므로
f(n-1)번씩 소요된다고 할 수 있다.
따라서 f(n) = 1 + 2*f(n-1)으로 표현할 수 있다.
 
f(1) = 1
f(2) = 3
f(3) = 1 + 2*3 = 7
 
규칙을 살펴보면 결국 f(n) = 2^n - 1이라는 것을 도출해낼 수 있다.
 
다음은 코드로 어떻게 구현할 것인지에 대해서 알아보자.
 
문제에 대한 코드는 다음과 같다.

N = int(input())
print(2**N - 1)
def hanoi(N, start, temp, end):
    if N == 1:
        return print(start, end)
    if N <= 20:
        hanoi(N - 1, start, end, temp)
        print(start, end)
        hanoi(N - 1, temp, start, end)
hanoi(N, 1, 2, 3)

 
일단 n == 1일 때는 원판을 한 번만 옮기는, 종료 조건이 될 것이다.
 
그리고 나머지 경우는 원판을 옮기는 과정을 다음과 같이 크게 나눌 수있다.
 
시작 - > 임시로 원판들을 옮기는 경우
시작에 있는 가장 큰 원판을 목표 기둥으로 옮기는 경우
임시 -> 목표로 원판들을 옮기는 경우
 
첫번째 경우에서는 목표 기둥을 임시 기둥으로 옮기는 데에 쓸 것이고,
세번째 경우에서는 시작 기둥을 임시 기둥으로 사용하게 된다.
 
그리고 첫번째, 세번째 경우에는 n -1개의 원판을 옮기는 행위를 해야한다.
즉, 재귀 호출이 필요한 것이다.