하노이 탑 알고리즘: Python, C++ Code

하노이타워란?

하노이 탑은 세 개의 막대와 크기가 점점 작아지는 원판들을 쌓아 올린 수학 퍼즐입니다. 프랑스 수학자 에두아르 루카스가 1883년에 이 퍼즐을 소개했기 때문에 브라마의 탑 또는 루카스 탑이라고도 불립니다. 이 퍼즐은 세 개의 막대 사이에서 금 원판을 움직이는 전설에 기반을 두고 있습니다.

이 퍼즐은 세 개의 막대와 여러 개의 원반이 쌓여 있는 형태로 구성되어 있습니다. 막대는 원형 탑처럼 배열되어 있어 큰 원반은 맨 아래에, 작은 원반은 맨 위에 쌓입니다.

처음에 우리는 세 개의 막대 또는 못을 받게 됩니다. 그중 하나(예시에서는 A 막대)에는 모든 원반이 쌓여 있습니다. 목표는 몇 가지 특정 규칙을 준수하면서 원반 더미 전체를 한 막대(A)에서 다른 막대(C)로 옮기는 것입니다.

퍼즐의 초기 설정은 다음과 같습니다.

하노이탑 문제

그리고 이것이 최종 목표입니다:

하노이 타워의 규칙

하노이 탑을 이용할 때 지켜야 할 필수 규칙은 다음과 같습니다.

• 퍼즐의 초기 상태에서는 모든 원반이 첫 번째 막대 위에 쌓여 있습니다.
• 최종 상태에서는 첫 번째 막대의 모든 디스크가 두 번째 막대 또는 세 번째 막대 위에 쌓입니다.
• 한 번에 하나의 디스크만 한 막대에서 다른 막대로 이동할 수 있습니다.
• 막대의 가장 위쪽에 있는 원반만 움직일 수 있습니다.
• 디스크는 더 작은 디스크 위에 올려놓을 수 없습니다.

원래 전설은 64개의 원반을 움직이는 것에 관한 것이었습니다. 사제들은 규칙에 따라 한 번에 하나의 원반만 움직일 수 있었습니다. 전설에 따르면, 만약 그들이 이 일을 완수하면 세상이 멸망할 것이라는 예언이 있었습니다. 시간 복잡도 분석 부분에서, n개의 원반으로 이루어진 하노이 탑을 만드는 데 2^n – 1번의 이동이 필요함을 보여드리겠습니다.

따라서 사제들이 원반 하나를 움직이는 데 1초가 걸렸다면, 퍼즐을 푸는 데 걸리는 총 시간은 2^64 - 1초, 즉 대략 584,942,417,356년 26일 7시간 15초가 됩니다.

하노이 타워 알고리즘

하노이 탑 문제를 푸는 가장 일반적인 방법은 재귀 알고리즘입니다. 먼저 두 개의 막대를 시작점과 끝점으로 선택하고, 남은 막대 하나는 보조 막대 또는 도우미 막대 역할을 합니다.

하노이 타워 퍼즐을 푸는 단계는 다음과 같습니다.

• 소스 페그에서 상단 n-1개의 디스크를 헬퍼 페그로 이동합니다.
• n번째 디스크를 출발점에서 목적지점으로 이동합니다.
• 보조 핀에 있는 나머지 n-1개의 원반을 목적지 핀으로 옮기세요.

참고 : 디스크가 하나뿐이라면 소스에서 대상으로 직접 이동할 수 있습니다.

하노이탑 퍼즐 푸는 방법

세 개의 디스크를 예로 들어 알고리즘을 설명하겠습니다. A 핀을 소스, B 핀을 헬퍼, C 핀을 대상으로 가정합니다.

단계 1) 처음에 모든 원반은 A 기둥에 쌓여 있습니다.

이 단계에서는 소스 = A 핀, 대상 = C 핀, 도우미 = B 핀이 됩니다.

이제 상위 n-1개 디스크를 소스에서 도우미로 이동해야 합니다.

참고 : 한 번에 하나의 디스크만 이동할 수 있지만, 이 단계를 통해 3개의 디스크로 이루어진 문제가 2개의 디스크로 이루어진 문제로 축소되고, 이는 재귀 호출을 통해 처리됩니다.

단계 2) A 지점에서 B 지점을 대상으로 재귀 호출을 할 때, C 지점을 도우미로 사용합니다.

이제 두 개의 원반을 사용하는 동일한 하노이 탑 문제의 1단계로 돌아왔음을 알 수 있습니다. n-1(즉, 1개)개의 원반을 출발점에서 보조점으로 옮기면, 보조점은 가장 작은 원반을 A 기둥에서 C 기둥으로 옮깁니다.

이 단계에서는 출발지 = A 핀, 목적지 = B 핀, 보조자 = C 핀입니다.

단계 3) 알고리즘에 따르면 n번째(2번째) 디스크가 이제 목적지인 B 핀으로 전송됩니다.

이 단계에서는 출발지 = A 핀, 목적지 = B 핀, 보조자 = C 핀입니다.

단계 4) 이제 알고리즘의 세 번째 단계에 따라 n-1번째 디스크(첫 번째 디스크)를 보조 핀 C에서 목적지 핀 B로 이동합니다.

이 단계에서는 출발지 = A 핀, 목적지 = B 핀, 보조자 = C 핀입니다.

단계 5) 재귀 호출이 완료되면 알고리즘의 첫 번째 단계에서 설정했던 이전 상태로 돌아갑니다.

단계 6) 두 번째 단계에서는 디스크 3을 소스 핀 A에서 대상 핀 C로 이동합니다.

이 단계에서는 출발지 = A 핀, 목적지 = C 핀, 보조자 = B 핀입니다.

단계 7) 다음 작업은 나머지 디스크들을 보조 디스크(B 핀)에서 목적지 디스크(C 핀)로 옮기는 것입니다. 이번에는 원래 소스 디스크(A 핀)를 보조 디스크로 사용하겠습니다.

단계 8) 두 개의 디스크를 동시에 이동할 수 없으므로 디스크 1에 대해 재귀 호출을 수행합니다. 저희에 따르면 연산이 단계의 목적지는 A 핀입니다.

이 단계에서는 출발지 = B 핀, 목적지 = A 핀, 보조자 = C 핀입니다.

단계 9) 재귀 호출이 완료되었습니다. 이제 디스크 2를 소스에서 대상으로 이동합니다.

이 단계에서는 출발지 = B 핀, 목적지 = C 핀, 보조자 = A 핀입니다.

단계 10) 마지막으로 나머지 n-1번째 디스크(디스크 1)를 헬퍼에서 대상으로 이동합니다.

이 단계에서는 출발지 = A 핀, 목적지 = C 핀, 보조자 = B 핀입니다.

별명 Code 하노이 탑을 위해

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

프로그램 코드 C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

출력:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

프로그램 코드 Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

출력:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

하노이의 탑의 복잡성

다음은 하노이 탑의 시간적, 공간적 복잡성입니다.

1) 시간 복잡도:

알고리즘을 되돌아보면, 우리는 호출할 때마다 (n-1)개의 디스크에 대해 두 번씩 재귀 호출을 합니다. 각 (n-1)개의 재귀는 ((n-1)-1)개의 재귀로 분해되고, 이런 식으로 단일 디스크 기본 사례에 도달할 때까지 계속됩니다.

디스크 3개용:

• 디스크 3는 디스크 2에 대한 재귀 함수를 두 번 호출합니다.
• 디스크 2는 디스크 1에 대한 재귀 함수를 두 번 호출합니다.
• 디스크 1은 일정한 시간 간격으로 움직이므로 세 개의 디스크에 대한 계산을 할 시간이 충분합니다.

반복으로 표현됨:

= 2 × (두 개의 디스크를 푸는 데 걸리는 시간) + 디스크 3을 이동하는 데 걸리는 상수 시간

= 2 × (원반 하나를 푸는 데 걸리는 시간 2배 + 두 번째 원반을 이동시키는 데 걸리는 상수 시간) + 세 번째 원반을 이동시키는 데 걸리는 상수 시간

= (2 × 2) × 디스크 1 이동 시간 + 2 × 디스크 2 이동 시간 + 디스크 3 이동 시간

디스크가 n개인 경우, 이는 다음과 같습니다.

2^n-1 × 원판 1 + 2를 이동시키는 데 걸리는 상수 시간^n-2 × 원판 2를 이동하는 데 걸리는 상수 시간 + ….

이 기하급수의 합은 O(2)입니다.ⁿ – 1), 이는 다음과 같이 간소화됩니다. O (2ⁿ)지수적인 시간 복잡도를 갖는다.

2) 공간 복잡성:

하노이 탑 알고리즘의 공간 복잡도는 O(n)입니다. 재귀 호출은 스택을 사용하는데, 스택의 최대 깊이는 디스크의 개수인 n과 같습니다. 따라서 공간 복잡도가 O(n)인 것입니다.

자주 묻는 질문