[BOJ] 하노이 탑 이동순서

---

코드

import sys
input = sys.stdin.readline

def hanoiRecursive(n, fr, to):
    axis = [1,2,3]
    axis.remove(fr)
    axis.remove(to)
    otherAxis = axis[0]

    if n == 1:
        print(fr, to)
        return
        
    # 1번부터 n-1번 원반을 다른 비어있는 축으로 옮기는 하위 문제를 재귀적으로 푼다.
    hanoiRecursive(n-1, fr, otherAxis)
    # n번 원반을 최종적으로 옮겨야 할 축으로 옮긴다.
    print(fr, to)
    # 1번부터 n-1번 원반을 다른 비어있는 축에서 최종적으로 옮겨야 할 축으로 옮기는 하위 문제를 재귀적으로 푼다.
    hanoiRecursive(n-1, otherAxis, to)

n = int(input())
print(2**n - 1)
hanoiRecursive(n, 1, 3)

결과

풀이 방법

• 하노이 탑 알고리즘을 재귀로 구현하는 문제이다.
• 1. 1번부터 n-1번 원반을 다른 비어있는 축으로 옮기는 하위 문제를 재귀적으로 푼다.
• 2. n번 원반을 최종적으로 옮겨야 할 축으로 옮긴다.
• 3. 1번부터 n-1번 원반을 다른 비어있는 축에서 최종적으로 옮겨야 할 축으로 옮기는 하위 문제를 재귀적으로 푼다.
• 탈출 조건은, 1개 원반을 최종 목표축으로 옮기는 경우로, n == 1이면 현재 축(fr)에서 최종 축(to)으로 옮기는 과정을 출력하고 리턴한다.
• 또한 각 함수 호출에서 '다른 비어있는 축'을 구하기 위해 axis 리스트를 사용하였다.
• 하노이 탑의 최소이동횟수는 2^N-1이다.

---