Computer >> 컴퓨터 >  >> 프로그래밍 >> 프로그래밍

하노이 타워(Tower of Hanoi) 문제 완벽 정리: 규칙부터 재귀 알고리즘, C++ 구현까지

하노이 타워란 무엇인가?

하노이 타워(Tower of Hanoi)는 전 세계적으로 유명한 수학 퍼즐 문제입니다. 이 문제는 세 개의 기둥과 n개의 원반(디스크)으로 구성됩니다. 처음에는 모든 원반이 첫 번째 기둥(출발지)에 크기 순서대로 쌓여 있으며, 최종적으로 모든 원반을 세 번째 기둥(목적지)으로 옮겨야 합니다. 이때 두 번째 기둥은 중간 과정에서 원반을 임시로 옮겨두는 보조 기둥 역할을 합니다.

하노이 타워의 규칙

원반을 옮길 때는 반드시 아래 세 가지 규칙을 지켜야 합니다.

  • 한 번의 이동으로는 단 하나의 원반만 옮길 수 있습니다.
  • 각 기둥에서는 가장 위에 있는 원반만 집어 들 수 있습니다.
  • 큰 원반을 작은 원반 위에 놓을 수 없습니다.

재귀를 활용한 해결 방법

하노이 타워 문제는 재귀(recursion)를 사용하면 매우 직관적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. 먼저 재귀 호출을 통해 맨 위의 (n-1)개 원반을 출발지 기둥에서 보조 기둥으로 옮깁니다.
  2. 그다음 남아 있는 가장 큰 원반 하나를 출발지에서 목적지 기둥으로 옮깁니다.
  3. 마지막으로 재귀 호출을 통해 보조 기둥에 있는 (n-1)개의 원반을 목적지 기둥으로 옮깁니다.

참고로 n개의 원반을 옮기는 데 필요한 최소 이동 횟수는 2ⁿ − 1번입니다. 예를 들어 원반이 3개라면 7번의 이동으로 문제를 해결할 수 있습니다.

입력 및 출력 예시

입력:
원반 개수: 3

출력:
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

알고리즘

하노이 타워 알고리즘은 다음과 같은 함수 형태로 정의할 수 있습니다.

toh(n, s, a, d)

입력: 원반의 개수(n), 출발지(s), 보조(a), 목적지(d)

출력: 규칙을 지키면서 원반을 출발지에서 목적지로 옮기는 전체 이동 과정

Begin
    if n = 1, then
        display move disc from s to d
    toh(n-1, s, d, a)

    display move disc from s to d
    toh(n-1, a, s, d)
End

C++ 구현 예제

위 알고리즘을 C++ 코드로 구현한 예제입니다. static 변수를 활용해 이동 횟수를 함께 출력합니다.

#include<iostream>
using namespace std;

void TOH(int n, char s, char a, char d) {
    static int count = 0;          // 이동 횟수 저장
    if(n == 1) {
        count++;
        cout << count<< ". Move disk " << n << " from "<<s <<" to "<<d<<endl;
        return;                    // 원반이 하나일 때의 기저 사례(base case)
    }

    TOH(n-1, s, d, a);             // 재귀 호출
    count++;
    cout << count<< ". Move disk " << n << " from "<<s <<" to"<<d<<endl;
    TOH(n-1, a, s, d);
}

int main() {
    int n;
    cout << "Enter the number of disks: ";
    cin >> n;
    TOH(n, 'A','B','C');
}

실행 결과

Enter the number of disks: 3
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

정리

하노이 타워는 재귀의 동작 원리를 학습하기에 가장 좋은 대표적인 예제입니다. 문제를 작은 부분 문제로 나누어 해결하는 분할 정복(Divide and Conquer) 사고방식을 익히는 데 큰 도움이 되며, 시간 복잡도는 O(2ⁿ)으로 원반 개수가 늘어날수록 이동 횟수가 지수적으로 증가한다는 점도 함께 기억해 두면 좋습니다.