[알고리즘] 하노이의 탑

하노이의 탑이란?

- 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키며 기둥 3개를 이용해서 원반을 옮김.

 

하노이의 탑 조건

(1) 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작(작은 원반이 위에, 큰 원반이 아래에 위치)

(2) 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮김

(3) 원반은 1개씩 옮길 수 있으며, 큰 원반은 작은 원반 위에 쌓을 수 없음

하노이의 탑 알고리즘

그룹으로 묶어서 옮기기

- 원반이 3개일 때

원반이 3개일 때

- 원반이 2개일 때

원반이 2개일 때

- 원반이 4개일 때

원반이 4개일 때

원반을 옮기는 과정을 코드로 구현

def move(no: int, x: int, y: int) -> None:
    # 원반 no개를 x기둥에서 y기둥으로 옮김
    if no > 1:
        move(no - 1, x, 6 - x - y)

    print(f"원반 [{no}]을(를) {x}기둥에서 {y}기둥으로 옮깁니다.")

    if no > 1:
        move(no - 1, 6 - x - y, y)

print("하노이의 탑을 구현합니다.")
n = int(input("원반의 개수를 입력하세요.: "))

move(n, 1, 3) # 1기둥에 쌓인 원반 n개를 3기둥으로 옮김

실행 결과 하노이의 탑을 구현합니다. 원반의 개수를 입력하세요.: 3 원반 [1]을(를) 1기둥에서 3기둥으로 옮깁니다. 원반 [2]을(를) 1기둥에서 2기둥으로 옮깁니다. 원반 [1]을(를) 3기둥에서 2기둥으로 옮깁니다. 원반 [3]을(를) 1기둥에서 3기둥으로 옮깁니다. 원반 [1]을(를) 2기둥에서 1기둥으로 옮깁니다. 원반 [2]을(를) 2기둥에서 3기둥으로 옮깁니다. 원반 [1]을(를) 1기둥에서 3기둥으로 옮깁니다.

no가 3일 때 move( ) 함수의 동작

• 이 프로그램에서는 기둥 번호를 정숫값 1, 2, 3으로 나타냄
• 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 위치에 있든 중간 기둥은 (6 - x - y)로 구할 수 있음
• 원반을 그룹으로 묶어서 옮기는 과정을 재귀로 구현