[백준] 1914. 하노이 탑
문제
세 개의 장대가 있고 첫 번째 장대에는 지름이 서로 다른 n개의 원판이 쌓여있다. 각 원판은 지름이 긴 순서대로 쌓여있다.
이제 내가 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 원판을 옮기려한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
N이 20 이하일 경우에는 두 번째 줄부터 수행 과정을 출력한다.
두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.
풀이
곧바로 N이 1, 2, 3일 때 출력이 어떻게 나오는지 확인해보자.
이 과정은 문제에 숨어있는 패턴을 찾기 위함인데, 여기서 찾아낸 패턴이 N이 더 커지더라도 성립하는지에 대해 계속해서 의심해야한다.
- N = 1
| 1 | |
|---|---|
| 1 | 3 |
- N = 2
| 3 | |
|---|---|
| 1 | 2 |
| 1 | 3 |
| 2 | 3 |
- N = 3
| 7 | |
|---|---|
| 1 | 3 |
| 1 | 2 |
| 3 | 2 |
| 1 | 3 |
| 2 | 1 |
| 2 | 3 |
| 1 | 3 |
문제풀이를 위한 핵심 패턴이 떠오르는가?
위 과정을 머리속으로 또는 직접 그려봤을 때 한 가지 생각나는 것은 가장 큰 원판이 세 번째 장대에 끼워지려면
무조건 나머지 원판들은 전부 두번째 장대에 끼워져있는 상태여야 한다는 것이다.
모든 원판을 세 번째 장대로 옮기기 위한 방법을 간단하게 정리하면 다음과 같다.
- 마지막 원판을 제외한 모든 원판을 두번째 장대로 옮긴다.
- 마지막 원판을 세번째 장대로 옮긴다.
- 나머지 원판을 크기 순서대로 세번째 장대로 옮긴다.
여기서 원판을 규칙에 맞게 하나씩 옮기는 과정이 반복되고 있는걸 볼 때 재귀 함수를 이용하여 풀 수 있을 것 같다는 생각이 들었는데,
다른 훌륭하신 분들의 문제 풀이를 살펴보면, 좀 더 체계적으로 확실하게 재귀를 전력으로 사용할 수 있는가에 대해서 고민한 흔적들이 보인다.
우선 재귀 알고리즘이라는 것은 어떤 함수가 내부에서 자기 자신을 호출하여 작업을 수행하는 알고리즘을 말한다.
같은 함수를 호출하는 것이기 때문에 입력과 출력의 값은 다르겠지만 형태는 항상 같다.
즉 같은 형태의 입력의 값이 조금씩 바뀌면서 종료조건을 만족할 때 까지 동작하는 것이 바로 재귀 함수이다.
Hanoi(N)이라는 함수가 N개의 원판을 다른 곳으로 옮기는 함수라고 정의했을 때,
재귀 함수를 이 문제에 적용하기 위해서는 Hanoi(N)에서 Hanoi(N-1)이 발견되는지를 확인해야만 한다.
Hanoi(3)이 수행되는 과정에서 Hanoi(2)가 수행이 되는가? -> 그렇다.
- 가장 큰 3번째 원판을 옮기기 위해서는 그 위에 있던 두개의 원판이 하나의 장대에 끼워져있어야한다. -> Hanoi(2)
- 나머지 두개의 원판을 세번째 원판위로 옮긴다 -> Hanoi(2)
이런식으로 재귀 함수를 전략으로 사용할 수 있는지에 대한 것을 확인할 수 있다.
재귀함수를 문제풀이 전략으로 잡았다면 이제 남은 것은 재귀식을 구체화하는 일이다.
이때 내가 위에서 찾은 모든 원판을 세 번째 장대로 옮기기 위한 방법을 사용한다.
- 마지막 원판을 제외한 모든 원판을 두번째 장대로 옮기는 것을 구체화하면 Hanoi(원판 개수, 출발지, 경유지, 목적지)라고 할 때 Hanoi(N-1, 1, 3, 2)
- 마지막 원판을 세번째 장대로 옮기는 것은 Hanoi(1, 1, x, 3)
- 나머지 원판을 크기 순서대로 장대로 옮기는 것은 Hanoi(N-1, 2, 1, 3)
그러면 이제 코드를 작성해보자
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def Hanoi(n, start, way, end):
"""
args:
int n: Number of stencil?
int start: start point
int way: way point
int end: end point
"""
if n == 1:
li.append([start, end])
return
else:
Hanoi(n-1, start, end, way)
Hanoi(1, start, way, end)
Hanoi(n-1, way, start, end)
li = []
N = int(input())
Hanoi(N, 1, 2, 3)
if N <= 20:
print(len(li))
for i,j in li:
print(i, j)
else:
print(len(li))
이 코드로 끝인줄 알았지만 실제로 제출해보니 메모리 초과가 되었다.
결국 N의 개수에 따른 반복 횟수를 계산하는 계산식을 정의해야한다.
어렵다고 생각이 들지만 이미 재귀식을 구체화해논 우리에겐 간단하다. \(Hanoi(N) = \begin{cases} 1, & \mbox{if } N==1 \\ 2\times Hanoi(N-1) + 1, & \mbox{if } N>1 \end{cases}\) 여기서 Hanoi(N-1)을 원판의 개수에 따른 식으로 바꾼다면 결국 Hanoi(N)의 이동횟수 Hanoi_n = 2^n - 1
따라서 코드를 수정하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def Hanoi(n, start, way, end):
"""
args:
int n: Number of stencil?
int start: start point
int way: way point
int end: end point
"""
if n == 1:
print(start, end)
return
else:
Hanoi(n-1, start, end, way)
Hanoi(1, start, way, end)
Hanoi(n-1, way, start, end)
N = int(input())
if N <= 20:
print(2**N - 1)
Hanoi(N, 1, 2, 3)
else:
print(2**N - 1)
재귀함수, 너무 어렵다.