이 포스트에서는 ‘하노이의 탑’에 대해 설명합니다.
※ 이 포스트는 ChatGPT의 도움으로 작성되었습니다.
하노이의 탑(Tower of Hanoi)은 19세기 프랑스 수학자 에두아르 뤼카(Édouard Lucas)에 의해 고안된 퍼즐입니다. 이 퍼즐은 세 개의 막대와 그 위에 쌓인 여러 개의 원판으로 구성됩니다. 원판은 크기가 다른 여러 개가 있으며, 막대 위에 큰 원판이 작은 원판 아래에 놓이는 순서로 쌓여 있습니다.
원판들을 모두 한 막대에서 다른 막대로 옮기는 것이 목표이며, 이동 규칙은 다음과 같습니다:
- 한 번에 한 개의 원판만 이동할 수 있습니다.
- 큰 원판은 작은 원판 위에 놓일 수 없습니다.
- 처음에는 모든 원판이 첫 번째 막대에 쌓여 있어야 하며, 마지막에는 모든 원판이 세 번째 막대에 옮겨져 있어야 합니다.
만약 원판이 1개라면, 출발 막대(1번)에서 도착 막대(3번)으로 바로 옮기면 끝이므로 최소 이동 횟수는 1회입니다. 여기서 원판 하나가 더 늘어나 2개가 된다면, 우선 맨 위의 작은 원판을 보조 막대(2번)로 옮겨놓고, 아래의 큰 원판을 도착 막대로, 다시 보조 막대의 작은 원판을 도착 막대 위의 큰 원판으로 옮겨서 끝. 이렇게 최소 이동 횟수는 3회입니다.
만약 원판이 3개라면, 다음과 같습니다. 여기서는 원판 번호를 작은 순서대로 숫자로 매기며, 출발 막대를 A, 보조 막대를 B, 도착 막대를 C라고 하겠습니다.
- 1번 원판을 A에서 C로 옮깁니다.
- 2번 원판을 A에서 B로 옮깁니다.
- 1번 원판을 C에서 B로 옮깁니다.
- 3번 원판을 A에서 C로 옮깁니다.
- 1번 원판을 B에서 A로 옮깁니다.
- 2번 원판을 B에서 C로 옮깁니다.
- 1번 원판을 A에서 C로 옮깁니다.
이렇게 최소 이동 횟수는 7회로 늘어납니다. 처음 3회는 목적지만 바뀌었을 뿐 2개 옮길 때와 같은 순서이고, 그 다음은 맨 밑의 원판을 도착 막대로 옮긴 후, 나머지 2개를 3번에 걸쳐 옮기면 됩니다.
만약 원판이 4개라면 15회, 5개라면 31회, 6개라면 63회, 7개라면 127회 … 이런 식으로 원판이 하나씩 늘어날 때마다 최소 이동 횟수는 2배에서 +1만큼 늘어납니다. 이를 통해, 원판이 n장이라면 최소 이동 횟수는 2ⁿ-1임을 알 수 있습니다.
이 게임에는, 다음과 같은 믿거나 말거나인 전설이 있습니다.
고대 인도 베나레스에 있는 한 사원의 이야기
여기에는 다이아몬드로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 64개의 크기가 각각 다른 황금 원반이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한 번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다.
이 규칙으로 64개의 원반을 처음 놓여 있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 세상의 종말이 온다고 한다.
이 하노이의 탑 프로그램은 재귀법으로 코딩 가능하며, 파이썬으로 코딩한 결과는 다음과 같습니다.
def hanoi_tower(n, source, target, auxiliary):
if n == 1:
print(f"원판 1을 {source}에서 {target}으로 이동")
return
hanoi_tower(n - 1, source, auxiliary, target)
print(f"원판 {n}을 {source}에서 {target}으로 이동")
hanoi_tower(n - 1, auxiliary, target, source)
# 예시 실행
n = int(input("옮길 원판의 개수를 입력하세요: "))
hanoi_tower(n, 'A', 'C', 'B')
위 코드의 실행 결과는 다음과 같습니다. 원판 개수는 4개로 입력했다고 가정합니다.
옮길 원판의 개수를 입력하세요: 4 원판 1을 A에서 B으로 이동 원판 2을 A에서 C으로 이동 원판 1을 B에서 C으로 이동 원판 3을 A에서 B으로 이동 원판 1을 C에서 A으로 이동 원판 2을 C에서 B으로 이동 원판 1을 A에서 B으로 이동 원판 4을 A에서 C으로 이동 원판 1을 B에서 C으로 이동 원판 2을 B에서 A으로 이동 원판 1을 C에서 A으로 이동 원판 3을 B에서 C으로 이동 원판 1을 A에서 B으로 이동 원판 2을 A에서 C으로 이동 원판 1을 B에서 C으로 이동