하노이탑의 탄생
1883년, 프랑스 수학자 에두아르 뤼카(Édouard Lucas)가 흥미로운 퍼즐 하나를 세상에 공개했다. 세 개의 기둥과 크기가 서로 다른 원반들로 이루어진 이 게임은, 가장 큰 원반이 맨 아래 있고 위로 갈수록 작은 원반이 쌓여있는 구조이다.
게임의 규칙
하나의 기둥에 있는 모든 원반을 다른 기둥으로 옮기는 것이 목표이며, 다음 세 가지 규칙을 반드시 지켜야 한다
- 한 번의 하나의 원반만 이동할 수 있다
- 가장 위에 있는 원반만 이동할 수 있다(아래 원반을 강제로 빼낼 수 없음)
- 작은 원반 위에 큰 원반을 올릴 수 없다
3개 원반으로 이해하는 하노이탑
초기 상태
기둥 A 기둥 B 기둥 C | | | [1] | | [2] | | [3] | | ===== ===== =====
목표
원반 1, 2, 3을 기둥 A에서 기둥 C로 이동(기둥 B는 보조 기둥)
이동 과정
1단계: 원반 1을 A → C로 이동 기둥 A 기둥 B 기둥 C | | | | | | [2] | | [3] | [1] ===== ===== ===== 2단계: 원반 2를 A → B로 이동 기둥 A 기둥 B 기둥 C | | | | | | | | | [3] [2] [1] ===== ===== ===== 3단계: 원반 1을 C → B로 이동 기둥 A 기둥 B 기둥 C | | | | | | | [1] | [3] [2] | ===== ===== ===== 4단계: 원반 3을 A → C로 이동 (가장 큰 원반이 목표 지점에 도착) 기둥 A 기둥 B 기둥 C | | | | | | | [1] | | [2] [3] ===== ===== ===== 5단계: 원반 1을 B → A로 이동 기둥 A 기둥 B 기둥 C | | | | | | | | | [1] [2] [3] ===== ===== ===== 6단계: 원반 2를 B → C로 이동 기둥 A 기둥 B 기둥 C | | | | | | | | [2] [1] | [3] ===== ===== ===== 7단계: 원반 1을 A → C로 이동 (완성) 기둥 A 기둥 B 기둥 C | | | | | [1] | | [2] | | [3] ===== ===== =====
재귀적 사고
하향식 접근법으로 겉보기에는 복잡해 보이지만, 하향식 사고방식을 적용하면 간단해진다.
핵심 아이디어
문제는 나누어 접근하는 것으로 큰 문제(3개의 원반을 A → C로 이동)를 다음 세 개의 하위 문제로 분해한다
┌─────────────────────────────────────────────────┐
│ 하위 문제 1: 위의 2개 원반을 A → B로 이동 │
│ (C를 보조 기둥으로 사용) │
└─────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────┐
│ 핵심 작업: 가장 큰 원반(3번)을 A → C로 이동 │
└─────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────┐
│ 하위 문제 2: B에 있는 2개 원반을 B → C로 이동 │
│ (A를 보조 기둥으로 사용) │
└─────────────────────────────────────────────────┘
재귀 구조 시각화
hanoi(3개, A→C, B사용)
│
├─ hanoi(2개, A→B, C사용) ← 하위 문제 1
│ │
│ ├─ hanoi(1개, A→C, B사용)
│ │ │
│ │ ├─ hanoi(0개) → 종료 (기저 조건)
│ │ ├─ [원반 1: A→C 이동]
│ │ └─ hanoi(0개) → 종료
│ │
│ ├─ [원반 2: A→B 이동]
│ │
│ └─ hanoi(1개, C→B, A사용)
│ │
│ ├─ hanoi(0개) → 종료
│ ├─ [원반 1: C→B 이동]
│ └─ hanoi(0개) → 종료
│
├─ [원반 3: A→C 이동] ← 핵심 작업
│
└─ hanoi(2개, B→C, A사용) ← 하위 문제 2
│
├─ hanoi(1개, B→A, C사용)
│ │
│ ├─ hanoi(0개) → 종료
│ ├─ [원반 1: B→A 이동]
│ └─ hanoi(0개) → 종료
│
├─ [원반 2: B→C 이동]
│
└─ hanoi(1개, A→C, B사용)
│
├─ hanoi(0개) → 종료
├─ [원반 1: A→C 이동]
└─ hanoi(0개) → 종료
HanoiTower.java
public class HanoiTower {
/**
* 하노이탑 재귀 함수
*
* @param count 이동할 원반의 개수
* @param from 출발 기둥
* @param to 목표 기둥
* @param temp 보조 기둥
*/
public static void hanoi(int count, String from, String to, String temp) {
// 기저 조건: 옮길 원반이 없으면 종료
if (count == 0) {
return;
}
// 1단계: 위의 (count-1)개 원반을 from → temp로 이동
// (to를 보조 기둥으로 사용)
hanoi(count - 1, from, temp, to);
// 2단계: 가장 큰 원반을 from → to로 이동
System.out.println("원반 " + count + "를 " + from + "에서 " + to + "로 이동");
// 3단계: temp에 있는 (count-1)개 원반을 temp → to로 이동
// (from을 보조 기둥으로 사용)
hanoi(count - 1, temp, to, from);
}
public static void main(String[] args) {
System.out.println("=== 하노이탑 시작 ===");
System.out.println("3개의 원반을 A에서 C로 이동 (B를 보조 기둥으로 사용)\n");
hanoi(3, "A", "C", "B");
System.out.println("\n=== 하노이탑 완료 ===");
}
}
/*
### 실행 결과
=== 하노이탑 시작 ===
3개의 원반을 A에서 C로 이동 (B를 보조 기둥으로 사용)
원반 1을 A에서 C로 이동
원반 2를 A에서 B로 이동
원반 1을 C에서 B로 이동
원반 3를 A에서 C로 이동
원반 1을 B에서 A로 이동
원반 2를 B에서 C로 이동
원반 1을 A에서 C로 이동
=== 하노이탑 완료 ===
*/
함수 실행 과정
호출 스택의 동작 원리
초기 호출: `hanoi(3, "A", "C", "B")` #### 스택 레벨 1: hanoi(3, A, C, B) ``` ┌──────────────────────────────────┐ │ count=3, from=A, to=C, temp=B │ │ │ │ if (3 == 0) → false, 계속 진행 │ │ ↓ │ │ hanoi(2, A, B, C) 호출 ───→ │ 스택에 쌓임 └──────────────────────────────────┘ ``` #### 스택 레벨 2: hanoi(2, A, B, C) ``` ┌──────────────────────────────────┐ │ count=2, from=A, to=B, temp=C │ │ │ │ if (2 == 0) → false, 계속 진행 │ │ ↓ │ │ hanoi(1, A, C, B) 호출 ───→ │ 스택에 쌓임 └──────────────────────────────────┘ ``` #### 스택 레벨 3: hanoi(1, A, C, B) ``` ┌──────────────────────────────────┐ │ count=1, from=A, to=C, temp=B │ │ │ │ if (1 == 0) → false, 계속 진행 │ │ ↓ │ │ hanoi(0, A, B, C) 호출 ───→ │ 스택에 쌓임 └──────────────────────────────────┘ ``` #### 스택 레벨 4: hanoi(0, A, B, C) ★ 기저 조건 도달! ``` ┌──────────────────────────────────┐ │ count=0, from=A, to=B, temp=C │ │ │ │ if (0 == 0) → TRUE! │ │ return; 함수 종료 ───→ │ 스택에서 제거 └──────────────────────────────────┘ ``` #### 스택 레벨 3으로 복귀: hanoi(1, A, C, B) ``` ┌──────────────────────────────────┐ │ hanoi(0, A, B, C) 완료 │ │ ↓ │ │ 출력: "원반 1을 A에서 C로 이동" │ ← 실제 작업 수행! │ ↓ │ │ hanoi(0, B, C, A) 호출 │ → 즉시 return │ ↓ │ │ 함수 종료 ───→ │ 스택에서 제거 └──────────────────────────────────┘ ``` #### 스택 레벨 2로 복귀: hanoi(2, A, B, C) ``` ┌──────────────────────────────────┐ │ hanoi(1, A, C, B) 완료 │ │ ↓ │ │ 출력: "원반 2를 A에서 B로 이동" │ ← 실제 작업 수행! │ ↓ │ │ hanoi(1, C, B, A) 호출 ───→ │ 새로운 재귀 시작 └──────────────────────────────────┘ ``` 이러한 방식으로 스택이 쌓였다가 풀리면서 모든 원반이 정확한 순서로 이동한다.
매개변수 변화 추적
┌──────┬────────┬─────┬──────┬───────┬──────────────────────┐ │ 호출 │ count │ from│ to │ temp │ 의미 │ ├──────┼────────┼─────┼──────┼───────┼──────────────────────┤ │ 1 │ 3 │ A │ C │ B │ 3개를 A→C로 (B 보조) │ │ 2 │ 2 │ A │ B │ C │ 2개를 A→B로 (C 보조) │ │ 3 │ 1 │ A │ C │ B │ 1개를 A→C로 (B 보조) │ │ 4 │ 0 │ A │ B │ C │ 기저조건 → return │ │ │ │ │ │ │ [출력] 원반1: A→C │ │ 5 │ 0 │ B │ C │ A │ 기저조건 → return │ │ │ │ │ │ │ [출력] 원반2: A→B │ │ 6 │ 1 │ C │ B │ A │ 1개를 C→B로 (A 보조) │ │ 7 │ 0 │ C │ A │ B │ 기저조건 → return │ │ │ │ │ │ │ [출력] 원반1: C→B │ │ 8 │ 0 │ A │ B │ C │ 기저조건 → return │ │ │ │ │ │ │ [출력] 원반3: A→C │ │ 9 │ 2 │ B │ C │ A │ 2개를 B→C로 (A 보조) │ │ 10 │ 1 │ B │ A │ C │ 1개를 B→A로 (C 보조) │ │ 11 │ 0 │ B │ C │ A │ 기저조건 → return │ │ │ │ │ │ │ [출력] 원반1: B→A │ │ 12 │ 0 │ C │ A │ B │ 기저조건 → return │ │ │ │ │ │ │ [출력] 원반2: B→C │ │ 13 │ 1 │ A │ C │ B │ 1개를 A→C로 (B 보조) │ │ 14 │ 0 │ A │ B │ C │ 기저조건 → return │ │ │ │ │ │ │ [출력] 원반1: A→C │ │ 15 │ 0 │ B │ C │ A │ 기저조건 → return │ └──────┴────────┴─────┴──────┴───────┴───────────────────────┘
하노이탑이 재귀 학습에 좋은 이유
- 직관적인 분할: 큰 문제를 명확하게 작은 문제로 나눌 수 있다
- 명확한 규칙: 게임 규칙이 단순하여 이해하기 쉽다(어려운 듯 하지만)
- 하향식 사고: “어떻게”보다 “무엇을”에 집중하는 재귀의 본질을 보여준다
재귀는 복잡한 문제를 더 작은 동일한 문제로 나누어 해결하는 우아한 방법이다. 하노이탑은 이 철학을 완벽하게 보여주는 고전적 예제이다. 당연히 어렵다. 손으로 그림을 그려가며 따라하면 이해할 듯 하다가 또 어려워진다. 그래도 밥은 먹고 살아야하니 다시 공부해본다