하노이의 탑

재귀를 공부하기 좋은 알고리즘

 

 

# from_pos 출발 기둥

# bozo_pos 보조 기둥

# to_pos 도착 기둥

 

스택을 그려가면서 해보면 이해가 됨.

 

def hanoi(n, from_pos, bozo_pos, to_pos, depth):

	if n == 1:
   		print(from_pos, "->", to_pos, depth)
    hanoi(n-1, from_pos, to_pos, bozo_pos, depth+1)
    print(from_pos, "->", to_pos, depth)
    hanoi(n-1, bozo_pos, from_pos, to_pos, depth+1)
    
hanoi(3,"A","B","C",0)