하노이의 탑

하노이의 탑 알고리즘 문제는 재귀적으로 해결되는 대표적인 문제이다.

 

하노이의 탑 규칙

• 한번에 한 개의 원판만 이동 가능
• 더 작은 원판 위에 더큰 원판을 놓을 수 없다

 

하노이의 탑이 재귀적으로 해결되는 이유

• N개의 원판을 옮기기 위해서는 N-1개 원판을 옮기는 문제를 해결해야함.
• N개의 원판을 A -> C로 옮기는 과정
  • (재귀 호출) N-1 개의 원판을 A -> B로 이동
  • (직접 호출) N의 원판을 A -> C로 이동
  • (재귀 호출) N-1개의 원판을 B -> C로 이동 

N = 3일 경우 원판을 옮기는 과정

원판 1: A → C
원판 2: A → B
원판 1: C → B
원판 3: A → C
원판 1: B → A
원판 2: B → C
원판 1: A → C

 

def hanoi(n,start,to,via,move_list):
	if n == 1 :
		move_list.append([start,to])
		return move_list
	hanoi(n-1,start,via,to,move_list)	# N-1개의 원판을 A > B로 이동
	move_list.append([start,to])
	hanoi(n-1,via,to,start,move_list)	# N-1개의 원판을 B > c로 이동

	return move_list

def solution(n) :
	answer = []
	answer = hanoi(n,1,3,2,answer)
	return answer

 

N = 3 일경우 재귀호출 트리