1. Problem
2. Solution
# Hanoi 수행 과정을 담은 list(lst)를 return하는 함수
def play_hanoi(N, rod1, rod2, rod3):
if N == 1: # 원판의 갯수 N이 1일 때
lst.append([rod1, rod3]) # 장대1의 원판은 장대3으로 이동
return lst
# 원판의 갯수 N이 1이 아닐 때
play_hanoi(N - 1, rod1, rod3, rod2) # in detail
lst.append([rod1, rod3]) # 가장 밑에 있는 원판 장대1에서 장대3으로 이동
play_hanoi(N - 1, rod2, rod1, rod3) # in detail
return lst
N = int(input())
lst = []
result = play_hanoi(N, 1, 2, 3)
print(len(result)) # 최소 이동(수행 과정) 횟수 출력
for i in range(len(result)):
print(str(result[i][0]) + ' ' + str(result[i][1])) # lst에 저장된 수행 과정 출력3. Detail
Hanoi 원리를 살펴보자.
-
원판의 갯수 N이 1일 경우
장대1에 있는 원판1을 장대3으로 옮긴다. (rod1 ▶ rod3) -
원판의 갯수 N이 2일 경우
* (중요) 장대1의 가장 밑에 있는 원판2를 장대3으로 옮겨야 한다.
1. 장대1에 있는 원판1을 장대2로 옮긴다. (rod1 ▶ rod2)
2.* 장대1에 있는 원판2를 장대3으로 옮긴다. (rod1 ▶ rod3)
3. 장대2에 있는 원판1을 장대2로 옮긴다. (rod2 ▶ rod3) -
원판의 갯수 N이 3일 경우
* (중요) 장대1의 가장 밑에 있는 원판3를 장대3으로 옮겨야 한다.
1. 장대1에 있는 원판1을 장대3로 옮긴다. (rod1 ▶ rod3)
2. 장대1에 있는 원판2을 장대2로 옮긴다. (rod1 ▶ rod2)
3. 장대3에 있는 원판1을 장대2로 옮긴다. (rod3 ▶ rod2)
4.* 장대1에 있는 원판3을 장대3로 옮긴다. (rod1 ▶ rod3)
5. 장대2에 있는 원판1을 장대1로 옮긴다. (rod2 ▶ rod1)
6. 장대2에 있는 원판2을 장대3로 옮긴다. (rod2 ▶ rod3)
7. 장대1에 있는 원판1을 장대3로 옮긴다. (rod1 ▶ rod3) -
원판의 갯수 N이 4일 경우
* 장대1의 가장 밑에 있는 원판4를 장대3으로 옮겨야 한다.
1. 장대1에 있는 원판1, 2, 3을 장대2로 옮긴다.
2. * 장대1에 있는 원판4을 장대3로 옮긴다. (rod1 ▶ rod3)
3. 장대2에 있는 원판1, 2, 3을 장대3의 원판4 위로 옮긴다.
위의 경우의 수마다의 Hanoi 수행 과정들을 살펴보면 일정한 규칙을 찾을 수 있고, 일반화하여 생각해보면 모든 N의 경우에 중간 수행 과정에 해당하는 rod1 ▶ rod3 과정은 동일하고, 중간 수행 과정 전 후도 N = 3과 N = 1을 이용하여 재귀 호출을 적용할 수 있는 문제라는 것을 알 수 있다.
if N == 1: # 원판의 갯수 N이 1일 때
lst.append([rod1, rod3]) # 장대1의 원판은 장대3으로 이동
return lst위의 code 부분은 N == 1일 경우에 rod1 ▶ rod3을 lst라는 list에 append 하도록 한것이다.
# 원판의 갯수 N이 1이 아닐 때
play_hanoi(N - 1, rod1, rod3, rod2) # in detail
lst.append([rod1, rod3]) # 가장 밑에 있는 원판 장대1에서 장대3으로 이동
play_hanoi(N - 1, rod2, rod1, rod3) # in detail
return lst위의 code 부분은 N != 1일 경우에 위에서 일반화해서 살펴본 것처럼 중간 수행 과정 전 과정은 'play_hanoi(N - 1, rod1, rod3, rod2)', 후 과정은 'play_hanoi(N - 1, rod2, rod1, rod3)'와 같이 재귀 호출을 하도록 했다. 이때 N = 2라고 가정했을 때 rod1 ▶ rod2 -> rod1 ▶ rod3 -> rod2 ▶ rod3 과정으로 진행된다. 그러므로 'lst.append([rod1, rod3])'코드를 통해 lst에 [rod1, rod3]가 append 되기 때문에 중간 이전 과정은 [rod1, rod2]가 append 될 수 있도록 rod1 위치에는 rod1이 들어가야하고, rod3 위치에는 rod2가 들어가야하므로 'play_hanoi(N - 1, rod1, rod3, rod2)'와 같이 작성해주면 된다. 중간 이후 과정도 마찬가지로 [rod2, rod3]이 append 될 수 있도록 rod1 위치에는 rod2가 들어가야하고, rod3 위치에는 rod3이 들어가야하므로 'play_hanoi(N - 1, rod2, rod1, rod3)'와 같이 재귀 함수를 만들어주면 된다.
