[알고리즘 기초] 하노이의 탑 Tower of Hanoi

하노이의 탑은 유명한 수학 퍼즐로, 1883년에 프랑스 수학자 에두아르 루카스에 의해 발명되었으며, 재귀 개념을 설명하는데 자주 사용됩니다. 세 개의 기둥(탑)과 서로 다른 크기의 n개의 원판들로 이루어져 있습니다. 초기 상태에서는 원판들이 크기가 감소하는 순서로 기둥 A에 쌓여 있습니다. 이 문제는 특정한 규칙을 따라 원판들을 한 기둥에서 다른 기둥으로 옮기는 것을 목표로 합니다. 이 과정에서 보조 기둥을 활용합니다.

이 문제는 A, B, C라고 레이블된 세 개의 기둥(탑)과 크기가 다른 n개의 원판들로 구성됩니다. 처음에는 원판들이 기둥 A에 크기순으로 쌓여 있습니다. 목표는 다음 규칙을 지키면서 원판들을 모두 기둥 A에서 기둥 C로 옮기는 것입니다:

1. 한 번에 하나의 원판만 이동할 수 있습니다.
2. 더 큰 원판 위에 작은 원판을 놓을 수 없습니다.

하노이의 탑 퍼즐을 재귀적으로 해결하는 단계는 다음과 같습니다:

1. 기본 사례: 원판이 하나일 때 (n = 1), 바로 원판을 출발 기둥에서 목적지 기둥으로 옮깁니다.

2. 재귀적 단계:
   a. (n-1)개의 원판을 출발 기둥에서 보조 기둥으로 목적지 기둥을 보조 기둥으로 사용하여 옮깁니다.
   b. 가장 큰 원판 (n번째 원판)을 출발 기둥에서 목적지 기둥으로 옮깁니다.
   c. (n-1)개의 원판을 보조 기둥에서 목적지 기둥으로 출발 기둥을 보조 기둥으로 사용하여 옮깁니다.
   이 재귀적인 과정은 문제의 크기가 1이 될 때까지 계속됩니다. 그러면 기본 사례에 도달하게 됩니다.

하노이의 탑 문제를 해결하는 파이썬 코드:

def hanoi(count, begin, end, transit='C'):
    locations = [begin, end]
    if transit in locations:
        if 'A' in locations and 'C' in locations:
            transit = 'B'
        elif 'B' in locations and 'C' in locations:
            transit = 'A'
        else:
            transit = 'C'

    if count == 1:
        print(f'Disk{count}: {begin} -> {end}')
    else:
        hanoi(count - 1, begin, transit, end)
        print(f'Disk{count}: {begin} -> {end}')
        hanoi(count - 1, transit, end, begin)


hanoi(3, 'A', 'B')