하노이탑 문제

하노이탑 문제란

큰판이 작은판보다 반드시 아래에 배치되어야하는 규칙을 지키면서 탑을 한 지점에서 다른 지점으로 옮기는 문제이다.

아이디어

하노이탑 문제는 분할정복 기법으로 접근하여 풀 수 있다. 즉, 하나의 큰 문제를 여러개의 작은 문제로 쪼개어서 풀 수 있다.

설계

# 디스크 옮기기
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)
	

하노이탑 문제는 세개의 작은 문제로 쪼갤 수 있다.

① 밑의 판을 제외한 나머지 판들을 가운데 탑으로 임시 위치로 옮긴다.

② 처음 위치의 마지막 판을 목표 위치로 옮긴다.

③  임시 위치에 있던 위의 판들을 목표 위치로 옮긴다.

구현

스택과 재귀호출을 활용하여 솔루션을 구현한다. 스택은 하노이탑의 위치를 표현한다. 재귀호출은 분할정복기법을 적용하기 위해 사용한다.