하노이탑 문제란
큰판이 작은판보다 반드시 아래에 배치되어야하는 규칙을 지키면서 탑을 한 지점에서 다른 지점으로 옮기는 문제이다.
아이디어
하노이탑 문제는 분할정복 기법으로 접근하여 풀 수 있다. 즉, 하나의 큰 문제를 여러개의 작은 문제로 쪼개어서 풀 수 있다.
설계
# 디스크 옮기기
def move(from, to):
disk = tower[from].top()
tower[from].pop()
tower[to].push(disk)
# 하노이 탑 옮기기
def hanoi(n, from, temp, to):
if n == 0:
return
hanoi(n -1, from, to, temp)
move(from, to)
hanoi(n -1, temp, from, to)
하노이탑 문제는 세개의 작은 문제로 쪼갤 수 있다.
① 밑의 판을 제외한 나머지 판들을 가운데 탑으로 임시 위치로 옮긴다.
② 처음 위치의 마지막 판을 목표 위치로 옮긴다.
③ 임시 위치에 있던 위의 판들을 목표 위치로 옮긴다.
구현
스택과 재귀호출을 활용하여 솔루션을 구현한다. 스택은 하노이탑의 위치를 표현한다. 재귀호출은 분할정복기법을 적용하기 위해 사용한다.