하노이 탑 문제: 3개의 기둥이 있으며 한 기둥에 원판들이 쌓여있다. 그리고 아래 규칙에 따라 원판을 다른 기둥으로 이동시켜야 한다.
규칙: 한 번에 하나의 원판을 이동시킬 수 있으며, 큰 원판이 작은 원판 위에 있으면 안 된다.
문제 해결
문제를 일반화하기 전, 3개의 원판을 가진 하노이탑 문제를 고민해보면 아래 그림과 같다.
3개의 원판을 이동시키기 위해서는 먼저 2개의 원판을 임시 기둥(B)으로 옮겨야 한다. 그런 후, 가장 큰 원판을 목표 기둥(C)으로 옮길 수 있다.
같은 원리로 2개의 원판을 목표 기둥(B)으로 이동하기 위해서는 임시 기둥(C)으로 작은 원판을 이동해야 한다.
문제 일반화
1. n개의 원판을 옮기기 위해 n-1개의 원판을 목표 기둥이 아닌 임시 기둥으로 옮겨야 한다. (n≥2)
2. (n-1개의 원판을 모두 임시 기둥으로 이동했다면) n번째 원판을 목표 기둥으로 이동한다.
3. 임시 기둥으로 이동한 n-1개의 원판을 목표 기둥으로 이동한다.
문제를 도식화해보면 DFS(깊이 우선 탐색) 방식으로 동작이 수행되는 것을 확인할 수 있다.
Python 코드
위에서 일반화한 문제 해결 과정을 살펴보면 5번째 원판을 옮기기 위해 4번째 원판을 옮기고, 4번째 원판을 옮기기 위해 3번째 원판을 옮기고... 하는 형태로 문제를 해결해야 한다. 따라서, 재귀 함수를 활용하면 문제를 해결할 수 있다.
class Hanoi(object):
def __init__(self):
self._count = 0
def move_disks(self, num, before, after, via):
self._count += 1
if num == 1:
# 1번 원판(가장 위의 원판)을 이동
print(f"1번째 원판: {before} -> {after}")
else:
# n-1개의 원판을 임시 기둥으로 이동
self.move_disks(num - 1, before, via, after)
# n번째 원판을 목표 기둥으로 이동
print(f"{num}번째 원판: {before} -> {after}")
# 임시 기둥으로 이동한 원판을 목표 기둥으로 이동
self.move_disks(num - 1, via, after, before)
disk_num = int(input("옮길 원판의 갯수: "))
print()
hanoi = Hanoi()
hanoi.move_disks(disk_num, "A", "C", "B")
print(hanoi._count)
실행 예시:
옮길 원판의 갯수: 3
1번째 원판: A -> C
2번째 원판: A -> B
1번째 원판: C -> B
3번째 원판: A -> C
1번째 원판: B -> A
2번째 원판: B -> C
1번째 원판: A -> C
원판을 옮긴 횟수: 7