하노이 탑(Tower of Hanoi)은 유명한 수학 퍼즐입니다. 이 퍼즐은 세 개의 막대(기둥)와 크기가 서로 다른 여러 개의 원판으로 구성되며, 원판은 어떤 막대에든 끼워 넣을 수 있습니다. 게임은 한 막대에 원판들이 크기순으로 깔끔하게 쌓여 있는 상태에서 시작되며, 가장 작은 원판이 맨 위에 위치합니다. 목표는 이 원판 더미 전체를 세 번째 막대로 옮겨 동일한 형태의 스택을 만드는 것입니다.
하노이 탑의 규칙
퍼즐의 목표는 아래의 간단한 규칙을 지키면서 원판 전체를 다른 막대로 옮기는 것입니다.
- 한 번에 오직 하나의 원판만 이동할 수 있습니다.
- 각 이동은 한 스택의 맨 위 원판을 꺼내 다른 스택의 꼭대기에 올려놓는 방식으로 이루어집니다. 즉, 원판은 해당 스택의 최상단에 있을 때만 움직일 수 있습니다.
- 어떤 원판도 자신보다 작은 원판 위에 놓일 수 없습니다.
실행 예시
입력 — 3
출력 — A to B
A to C
B to C
A to B
C to A
C to B
A to B
설명 — 재귀 함수를 활용하여 하노이 탑 문제를 해결합니다. 원판이 3개인 경우 총 7번의 이동(2³ − 1)으로 모든 원판을 목표 막대로 옮길 수 있습니다.
C 코드 예제
#include<stdio.h>
void TOH(int n,char x,char y,char z) {
if(n>0) {
TOH(n-1,x,z,y);
printf("\n%c to %c",x,y);
TOH(n-1,z,y,x);
}
}
int main() {
int n=3;
TOH(n,'A','B','C');
}
출력 결과
A to B
A to C
B to C
A to B
C to A
C to B
A to B
코드 동작 원리
위 프로그램의 TOH 함수는 재귀적으로 동작합니다. n개의 원판을 x 막대에서 y 막대로 옮기기 위해 다음 세 단계를 수행합니다.
- 1단계: 먼저 n−1개의 원판을 보조 막대(z)로 옮깁니다.
TOH(n-1, x, z, y) - 2단계: 가장 큰 원판(맨 아래 원판)을 목표 막대(y)로 이동하고 화면에 출력합니다.
- 3단계: 보조 막대에 있던 n−1개의 원판을 목표 막대(y) 위로 옮깁니다.
TOH(n-1, z, y, x)
이 과정이 재귀적으로 반복되면서 원판이 1개 남을 때까지 분할 정복 방식으로 문제를 해결합니다. 하노이 탑 문제는 재귀 알고리즘의 대표적인 예제로, 이동 횟수는 2ⁿ − 1번이며 시간 복잡도는 O(2ⁿ)입니다.