하노이의 탑, 재귀 알고리즘

(1-1) 원반이 한 개면 그냥 옮기면 끝입니다. (종료 조건)

(1-2) 원반이 n개일 때

 

1. 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮깁니다.
( 3번 기둥을 보조 기둥으로 사용)

2. 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮깁니다.

3. 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮깁니다.

(1번 기둥을 보조 기둥으로 사용)

 

원반이 한 개일 때가 바로 '종료 조건'에 해당.

 

원반 n개 문제를 풀려면 n-1개 원반 문제를 풀어야 하는데,

이는 바로 '좀 더 작은 값으로 자기 자신을 호출' 하는 과정

따라서, 이 문제는 전형적인 재귀 호출 알고리즘에 해당.

 

#하노이의 탑
#입력 : 옮기려는 원반의 개수 n
#   옮길 원반이 현재 있는 출발점 기둥 from_pos
#   원반을 옮길 도착점 기둥 to_pos
#   옮기는 과정에서 사용할 보조 기둥 mid_pos
#출력 : 원반을 옮기는 순서

def hanoi(n, from_pos, to_pos, mid_pos):
    if n == 1:      # 원반 한개를 옮기는 문제면 그냥 옮기면 됨
        print(from_pos, "->", to_pos)
        return

    # 원반 n-1개를 aux_pos로 이동(to_pos를 보조 기둥으로)
    hanoi(n-1, from_pos, mid_pos, to_pos)
    # 가장 큰 원반을 목적지로 이동
    print(from_pos, "->", to_pos)
    # aux_pos에 있는 원반 n-1개를 목적지로 이동(from_pos를 보조 기둥으로)
    hanoi(n-1, mid_pos, to_pos, from_pos)


print("n = 1")
hanoi(1, 1, 3, 2)
print("n = 2")
hanoi(2, 1, 3, 2)
print("n = 3")
hanoi(3, 1, 3, 2)

 

 

 

 

 

 

<모두의 알고리즘with 파이썬> (이승찬 지음)