[수학/재귀] 백준 11729 하노이 탑 이동 순서 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11729번: 하노이 탑 이동 순서

 

 

 

2. 문제 풀이

1) 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다
2) 원판은 위에서부터 꺼내, 1개씩 이동한다

 

 재귀 문제의 대명사, '하노이탑 문제'입니다. 목표 지점까지 '맨 밑의 원판'부터 하나씩 재귀적으로 옮겨야 합니다.

 

 

 원판이 3개일 때를 예시로 들어보겠습니다. 하노이탑의 규칙에 따라, 목표 막대로 원판을 옮기려면 맨 아랫 원판부터 차근차근 쌓아야 합니다. 그러기 위해서 보조막대를 이용합니다.

 

 

 보조막대에 N-1개인 2개를 옮깁니다. 이렇게 해야, 목표 막대에 맨 아랫원판을 옮길 수 있습니다.

 

 

 자, 이제 목표 막대에 맨 아랫 원판을 옮겼습니다. 그다음으론, 2번째 원판을 쌓아야 합니다.

 

 

 위에서 했던 것과 똑같이 반복합니다. 이번에는 2번째 막대에서 '시작'해서 1번 막대를 보조로 사용합니다.

 

 

 N-1개인 1개를 보조 막대에 옮기고, 맨 아랫 원판을 목표 막대에 쌓습니다.

 

 

 원판이 1개 남았을 때는 보조막대 필요없이, 바로 목표 막대로 옮기면 됩니다.

 앞서 살펴본 과정을 일반화하면 아래와 같습니다.

 

옮겨야할 원판의 수를 N이라고 할 때,
1) N이 2개 이상이면, 보조 막대에 N-1개를 옮기고 맨 아랫 원판을 목표 막대에 옮긴다
2) N이 1개이면, 목표 막대에 옮기고 끝낸다

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 하노이의 탑 알고리즘
def hanoi_tower(n, start, end):
    # n이 1이 되면 종료
    if n == 1:
        print(start, end)
        return

    # 1단계, n-1개의 원판을 시작 막대에서 보조 막대로 옮김
    hanoi_tower(n-1, start, 6-start-end)
    
    # 2단계, 맨 아랫 원판을 시작 막대에서 목표 막대로 옮김
    print(start, end)
    
    # 다시 1, 2단계를 반복하기 위한 재귀호출
    hanoi_tower(n-1, 6-start-end, end)

# 입력
n = int(input())
print(2**n-1)  # 옮긴 횟수 K
hanoi_tower(n, 1, 3)

 위에서 설명한 과정을 코드로 구현했습니다.

 보조 막대의 번호는 [ 6 - 시작막대의 번호 - 목표 막대의 번호 ]로 구합니다. 1 + 2 + 3 = 6이기 때문에, start 막대와 end 막대의 번호를 빼주면 보조 막대의 번호를 구할 수 있습니다.