하노이 탑

순환 알고리즘

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다.

하노이 탑

하노이 탑은 세 개의 기둥과 크기가 다른 원반들로 이루어진 수학적 게임입니다. 게임의 목표는 한 기둥에 쌓여있는 원반들을 다음의 규칙에 따라 다른 기둥으로 옮기는 것입니다:

• 한 번에 하나의 원반만 옮길 수 있습니다.
• 각 기둥의 맨 위에 있는 원반만 이동할 수 있습니다.
• 큰 원반을 작은 원반 위에 올려놓을 수 없습니다.

하노이 탑에서 원판을 옮기는 방법은 다음과 같습니다.

1. 만약 원판이 하나일 때 : 한번에 옮김
2. 원판이 두개 이상일 때 : 보조 기둥을 사용해서 이동 : 가장 큰 디스크를 먼저 옮김

예를 들어 $A, B, C$기둥이 있고 $A\rightarrow C$로 이동하고 싶을 때, $A$에 두개의 디스크가 있다고 하면 다음과 같은 과정을 가집니다.

다음과 같은 과정으로 세개의 디스크가 있다고 하면 위의 두개, 아래의 한개를 두 덩어리로 하고 옮기면 됩니다. 즉, 재귀합니다.

Python 코드

def hanoi(n, start, temp, end):
    if n == 1:
        print(n, start, end)
    else:
        hanoi(n-1, start, end, temp)
        print(n, start, end)
        hanoi(n-1, temp, start, end)

input = sys.stdin.readline
n = int(input()) # Number of Disks
hanoi(n, 'A', 'B', 'C') # start, temp, end

• $h(3, A, B, C) - A \rightarrow C$
  • $h(2, A, C, B) - A \rightarrow B \uparrow$
    • $h(1, A, B, C) - A\rightarrow C \uparrow$
    • $h(1, C, A, B) - C \rightarrow B$
  • $h(2, B, A, C) - B\rightarrow C$
    • $h(1, B, C, A) - B\rightarrow A \uparrow$
    • $h(1, A, B, C) - A \rightarrow C$