![[Python] 백준(BOJ) 11729번 하노이 탑 이동 순서 (재귀)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdjlExh%2FbtrrKwzo1TD%2F1fQocoLk8uvPSjVivyaEg1%2Fimg.png)
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
예제 입력 1
3예제 출력 1
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3풀이
1. 옮긴 횟수
원판이 1개인 경우: 1번
( 1 → 3 )
| [1] |
1번째 ( 1 → 3 )
| [1] |
원판이 2개인 경우: 3번
( 1 → 2 ) ( 1 → 3 ) ( 2 → 1 )
| [ 1 ] | ||
| [ 2 ] |
1번째 ( 1 → 2 )
| [ 2 ] | [ 1 ] |
2번째 ( 1 → 3 )
| [ 1 ] | [ 2 ] |
3번째 ( 2 → 1 )
| [ 1 ] | ||
| [ 2 ] |
원판이 3개인 경우: 7번
( 1 → 3, 1 → 2, 3 → 2 ) ( 1 → 3 ) ( 2 → 1, 2 → 3, 1 → 3 )
| [ 1 ] | ||
| [ 2 ] | ||
| [ 3 ] |
1번째 ( 1 → 3 )
| [ 2 ] | ||
| [ 3 ] | [ 1 ] |
2번째 ( 1 → 2 )
| [ 3 ] | [ 2 ] | [ 1 ] |
3번째 ( 3 → 2 )
| [ 1 ] | ||
| [ 3 ] | [ 2 ] |
4번째 ( 1 → 3 )
| [ 1 ] | ||
| [ 2 ] | [ 3 ] |
5번째 ( 2 → 1 )
| [ 1 ] | [ 2 ] | [ 3 ] |
6번째 ( 2 → 3 )
| [ 2 ] | ||
| [ 1 ] | [ 3 ] |
7번째 ( 1 → 3 )
| [ 1 ] | ||
| [ 2 ] | ||
| [ 3 ] |
원판이 4개인 경우: 15번
( 1 → 3, 1 → 2, 2 → 1, 1 → 2, 3 → 1, 3 → 2, 1 → 2 ) ( 1 → 3 )
( 2 → 3, 2 → 1, 3 → 1, 2 → 3, 1 → 2, 1 → 3, 2 → 1 )
| [ 1 ] | ||
| [ 2 ] | ||
| [ 3 ] | ||
| [ 4 ] |
1번째 ( 1 → 3 )
| [ 2 ] | ||
| [ 3 ] | ||
| [ 4 ] | [ 1 ] |
2번째 ( 1 → 2 )
| [ 3 ] | ||
| [ 4 ] | [ 2 ] | [ 1 ] |
3번째 ( 2 → 1 )
| [ 3 ] | [ 1 ] | |
| [ 4 ] | [ 2 ] |
4번째 ( 1 → 2 )
| [ 1 ] | ||
| [ 4 ] | [ 3 ] | [ 2 ] |
5번째 ( 3 → 1 )
| [ 1 ] | ||
| [ 4 ] | [ 3 ] | [ 2 ] |
6번째 ( 3 → 2 )
| [ 1 ] | [ 2 ] | |
| [ 4 ] | [ 3 ] |
7번째 ( 1 → 2 )
| [ 1 ] | ||
| [ 2 ] | ||
| [ 4 ] | [ 3 ] |
8번째 ( 1 → 3 )
| [ 1 ] | ||
| [ 2 ] | ||
| [ 3 ] | [ 4 ] |
9번째 ( 2 → 3 )
| [ 2 ] | [ 1 ] | |
| [ 3 ] | [ 4 ] |
10번째 ( 2 → 1 )
| [ 1 ] | ||
| [ 2 ] | [ 3 ] | [ 4 ] |
11번째 ( 3 → 1 )
| [ 1 ] | ||
| [ 2 ] | [ 3 ] | [ 4 ] |
12번째 ( 2 → 3 )
| [ 1 ] | [ 3 ] | |
| [ 2 ] | [ 4 ] |
13번째 ( 1 → 2 )
| [ 3 ] | ||
| [ 2 ] | [ 1 ] | [ 4 ] |
14번째 ( 1 → 3 )
| [ 2 ] | ||
| [ 3 ] | ||
| [ 1 ] | [ 4 ] |
15번째 ( 2 → 1 )
| [ 1 ] | ||
| [ 2 ] | ||
| [ 3 ] | ||
| [ 4 ] |
옮긴 횟수가 1, 3, 7, 15, … 이므로 아래와 같은 점화식으로 표현해줄 수 있다.
$$a_{n} = 2a_{n-1}+1$$
$$( a_1 = 1,\ n = 2, 3, 4, \cdots )$$
양 변에 1을 더해주면
\begin{align}
&a_{n}+1 = 2a_{n-1}+2 \\
&\Rightarrow a_{n} +1 = 2(a_{n-1} +1)
\end{align}
\begin{align}
a_{n}+1 &= 2(a_{n-1}+1) \\
a_{n-1}+1 &= 2(a_{n-2}+1) \\
a_{n-2}+1 &= 2(a_{n-3}+1) \\
a_{n-3}+1 &= 2(a_{n-4}+1) \\
&\ \ \vdots \\
a_{2}+1 &= 2(a_{1}+1)
\end{align}
이 때 좌변끼리 곱하고 우변끼리 곱해주면
\begin{align}
&(a_{n}+1)(a_{n-1}+1)\cdots(a_{2}+1) = 2^{n-1}(a_{n-1}+1)(a_{n-2}+1)\cdots(a_{1}+1) \\
\end{align}
같은 항을 지워주면
\begin{align}
a_{n}+1 &= 2^{n-1}(a_{1}+1) \\
\Rightarrow a_n &= 2^n -1
\end{align}
따라서 옮긴 횟수는 이를 활용해 간단하게 구할 수 있다.
2. 수행과정
먼저 원판이 2개인 경우부터 보면 (1)을 옮기고 2를 옮기고 (1)을 옮긴다.
3개인 경우는 (1, 2)를 옮기고 3을 옮기고 (1, 2)를 옮긴다.
4개인 경우는 (1, 2, 3)을 옮기고 4를 옮기고 (1, 2, 3)을 옮긴다.
따라서 n개인 경우 (1, 2, 3 …, n-1)을 옮기고 n을 옮기고 (1, 2, 3 …, n-1)을 옮긴다
여기서 원판이 3개인 경우 (1, 2)를 옮기는 것이 원판 2개인 경우의 원판을 옮기는 것과 같으므로
2개의 원판을 옮기고 3번 원판을 옮기고 다시 2개의 원판을 옮기면 된다.
마찬가지로 원판이 4개인 경우 (1, 2, 3)을 옮기는 것이 원판 3개인 경우의 원판을 옮기는 것과 같으므로
3개의 원판을 옮기고 4번 원판을 옮기고 다시 3개의 원판을 옮기면 된다.
따라서 원판이 n개인 경우 n-1개의 원판을 옮기고 n번 원판을 옮기고 다시 n-1개의 원판을 옮기면 된다.
하지만 옮기는 위치가 다르므로 주의해야 한다.
따라서 다음과 같이 코드를 써줄 수 있다.
코드
def hanoi(n, start, end, middle): # n개의 원판을 start에서 end로 옮긴다
if n == 1:
return print(start, end) # 첫번째 원판을 start에서 end로 옮긴다
hanoi(n-1, start, middle, end) # n-1개의 원판을 start에서 middle로 옮긴다
print(start, end) # n번째 원판을 start에서 end로 옮긴다
hanoi(n-1, middle, end, start) # n-1개의 원판을 middle에서 end로 옮긴다
n = int(input())
print(2**n-1) # 옮긴 횟수
hanoi(n, 1, 3, 2) # n개의 원판을 1에서 3으로 옮긴다