[BOJ][Python] 11729번 하노이 탑 이동 순서

1. 문제

https://www.acmicpc.net/problem/11729

백준 11729 - 하노이 탑 이동 순서 문제 캡쳐

• 문제는 하노이 탑을 최소 이동으로 3번째 탑으로 옮겼을 때의 이동 횟수와 그 과정을 출력하는 것이다.
• 이 문제를 해결하기 위해서는 먼저 하노이 탑의 원반이 어떻게 이동을 해야하는 지부터 알아야 한다.

 

2. 하노이 탑 이동 알고리즘

하노이탑에서 원반을 최소 이동으로 옮기는 방법 예시

 

• 하노이 탑이 최소 이동하였을 때를 보면 위 그림과 같은 규칙을 갖고 있다.
• 원판이 총 5개 일 때를 예시로 들면, 3번째 탑으로 모두 옮기고 싶으면 첫 번째 원판(제일 큰 거)을 3번째로 옮기고 나머지 4개의 원판 기둥은 두 번째 탑으로 옮기게 된다. 두 번째 원판을 세 번째 탑으로 옮기려면 나머지 3개의 원판 기둥을 첫 번째 탑으로 옮기게 된다.

 

3. 코드 작성

import sys

n = int(sys.stdin.readline().strip())

def move_top(n, start, end):
    if n == 1:
        print(start, end)
        return
    
    index = [start, 1]
    if 2 not in [start, end]:
        index[1] = 2
    elif 3 not in [start, end]:
        index[1] = 3
    flag = 0

    for i in range(n-1, 0, -1):
        move_top(i, index[flag], index[1 - flag])
        print(index[flag], end)
        
        flag = 1- flag
    print(index[flag], end)
    
    
print(2**n - 1)
move_top(n, 1, 3)

4. 코드 설명

• 현 기둥 위치를 start, 옮기고 싶은 위치를 end, 나머지 하나의 기둥을 middle 이라고 했을 때, start에서 end로 원판들을 옮길 때 start, middle 기둥을 번갈아가며 점점 원판의 개수가 줄어들게 원판을 쌓고, 기둥에 쌓을 때마다 end 탑을 큰 원 순서로 쌓을 수 있다는 것을 볼 수 있다. 이러한 규칙들을 바탕으로 코드를 작성하였다.
• move_top 함수의 인자로는 원판의 개수 n, 처음 원판들이 쌓여있는 위치 start, 쌓고 싶은 위치 end을 주었다.
• middle에 해당하는 것을 찾아 index에 넣어주고, start와 middle을 번갈아가며 기둥을 만들어 주어야 하기 때문에 인덱스에 접근할 때 flag를 사용하였다. flag는 for문 안에서 한 번 반복될 때마다 1-flag를 하여 0 1 0 1 이렇게 인덱스를 번갈아 가며 사용할 수 있도록 하였다.
• 크게 보면 밑부터 큰 원판을 빼내는 것이므로 반복문은 큰 수부터 1까지 돌려주었다.
• 하노이 탑의 이동 횟수는 따로  2^n - 1을 출력해주었다.