[정글 알고리즘]-[중]-백준 1914 하노이 탑 - 재귀

📌 01 하노이 탑 02 외판원 순회

골드 5 · 재귀

[백준 1914] 하노이 탑
재귀의 정수를 맛보다

cedis · 2026.03  |  Python · 재귀 · 수학

재귀를 처음 배울 때 항상 따라오는 문제가 있다. 하노이 탑이다. 코드는 딱 10줄인데, 처음 보면 도대체 어떻게 돌아가는지 전혀 안 보인다. 이 글은 그 "왜 이게 되지?" 를 끝까지 파헤친 기록이다.

🔗 문제 링크: 백준 1914번 - 하노이 탑
N개의 원판을 기둥 1에서 기둥 3으로 옮기는 이동 횟수와 과정을 출력하라.
단, 큰 원판이 작은 원판 위에 놓일 수 없다. (N ≤ 100)

① 하노이 탑 규칙

기둥이 3개, 원판이 N개 있다. 규칙은 딱 두 가지다.

1

한 번에 원판 하나만 옮긴다

맨 위에 있는 원판만 집을 수 있다.

2

큰 원판이 작은 원판 위에 올라갈 수 없다

숫자가 큰 원판(아래쪽)은 항상 숫자가 작은 원판(위쪽) 아래에 있어야 한다.

N=3일 때 시작 상태는 이렇다. 기둥 1에 원판 3개가 쌓여 있고, 이걸 기둥 3으로 전부 옮겨야 한다.

시작 상태

기둥 1 (start)

1

2

3

기둥 2 (tmp)

기둥 3 (end)

→

목표 상태

기둥 1 (start)

기둥 2 (tmp)

기둥 3 (end)

1

2

3

② 핵심 아이디어: 재귀적 분해

처음에는 N개를 한 번에 생각하려다 막힌다. 하지만 이렇게 바꿔서 생각하면 단순해진다.

💡 핵심 생각 전환
"N개를 옮기는 방법" = "N-1개를 옮기는 방법" 을 두 번 쓰면 된다.

N=3을 예시로 단계를 쪼개보자.

1

원판 1~2 (위 N-1개)를 기둥 2(tmp)로 옮긴다

기둥 3을 임시로 사용한다. → dohanoi(n-1, start, tmp, end)

2

제일 큰 원판(3번)을 기둥 3(end)으로 옮긴다

이 한 칸만 직접 이동한다. → print(start, end)

3

원판 1~2를 기둥 2(tmp)에서 기둥 3(end)으로 옮긴다

기둥 1을 임시로 사용한다. → dohanoi(n-1, tmp, end, start)

📌 N=3 단계별 시각화

STEP 1 — 원판 1,2를 기둥 2로

기둥 1

3

기둥 2

1

2

기둥 3

STEP 2 — 원판 3을 기둥 3으로

기둥 1

기둥 2

1

2

기둥 3

3

STEP 3 — 원판 1,2를 기둥 3으로

기둥 1

기둥 2

기둥 3

1

2

3

③ 이동 횟수: 왜 2ⁿ - 1인가

위 3단계를 T(N)으로 표현하면 이렇다.

T(N) = T(N-1) + 1 + T(N-1) = 2·T(N-1) + 1

T(1) = 1 (원판 1개는 바로 옮기면 됨)

이 점화식을 풀면:

T(N) = 2ⁿ - 1

N=3: 2³-1 = 7번  |  N=4: 2⁴-1 = 15번  |  N=20: 1,048,575번

⚠️ 왜 코드에서 if n <= 20 일 때만 경로를 출력하나?
N=20이면 이동 횟수는 약 100만 번이다. N=100이면 2¹⁰⁰-1 — 이건 30자리 숫자로 출력 자체가 불가능에 가깝다.
그래서 이 문제는 이동 횟수만 출력할 때는 N≤100을 허용하고, 경로 출력은 N≤20으로 제한한 것이다.

⚠️ 이동 횟수 출력에 주의
N이 최대 100이기 때문에 2¹⁰⁰은 파이썬의 int로는 표현되지만 C/C++ 의 long long 은 오버플로우가 난다. 파이썬은 임의 정밀도 정수라서 2 ** n - 1 그대로 쓰면 된다.

④ 재귀 호출 트리 (N=3)

실제 호출 순서는 이렇게 펼쳐진다.

dohanoi(3, 1, 3, 2)
├─ dohanoi(2, 1, 2, 3) # 1,2번 원판을 1→2로
│ ├─ dohanoi(1, 1, 3, 2) # 1번 원판을 1→3으로
│ │ └─ BASE: print(1, 3) ▶ 1 3
│ ├─ print(1, 2) ▶ 1 2
│ └─ dohanoi(1, 3, 2, 1) # 1번 원판을 3→2로
│ └─ BASE: print(3, 2) ▶ 3 2
├─ print(1, 3) ▶ 1 3 ← 가장 큰 원판 이동
└─ dohanoi(2, 2, 3, 1) # 2,1번 원판을 2→3으로
   ├─ dohanoi(1, 2, 1, 3) # 1번 원판을 2→1로
   │ └─ BASE: print(2, 1) ▶ 2 1
   ├─ print(2, 3) ▶ 2 3
   └─ dohanoi(1, 1, 3, 2) # 1번 원판을 1→3으로
     └─ BASE: print(1, 3) ▶ 1 3

출력 순서 (N=3):  1 3 → 1 2 → 3 2 → 1 3 → 2 1 → 2 3 → 1 3  (총 7번 = 2³-1)

⑤ 한글 수도코드

함수 dohanoi(n, start, end, tmp):

만약 n == 1 이면
# 원판 1개: 그냥 바로 옮기면 됨 (베이스 케이스)
start → end 출력
종료

# 1단계: 위 n-1개를 tmp로 보내기 (end를 경유지로 사용)
dohanoi(n-1, start, tmp, end)

# 2단계: 가장 큰 원판을 end로 직접 이동
start → end 출력

# 3단계: tmp에 있는 n-1개를 end로 보내기 (start를 경유지로 사용)
dohanoi(n-1, tmp, end, start)

N 입력
2^N - 1 출력 # 이동 횟수
만약 N ≤ 20 이면
dohanoi(N, 1, 3, 2) 호출 # 경로 출력

⑥ 코드 한 줄씩 분석

def dohanoi(n, start, end, tmp):
    if n == 1:             # ① 베이스 케이스
        print(start, end)  # ② 원판 1개 → 바로 이동
        return

    dohanoi(n - 1, start, tmp, end)  # ③ 위 n-1개 → tmp로
    print(start, end)                   # ④ 가장 큰 원판 → end로
    dohanoi(n - 1, tmp, end, start)    # ⑤ n-1개 tmp → end로

n = int(input())
print(2 ** n - 1)         # ⑥ 이동 횟수: 2ⁿ-1
if n <= 20:               # ⑦ 경로 출력은 n≤20만
    dohanoi(n, 1, 3, 2)Python

번호	코드	의미
①	if n == 1	원판이 1개면 그냥 바로 옮기면 됨. 재귀의 종료 조건 (베이스 케이스)
②	print(start, end)	원판을 start 기둥에서 end 기둥으로 이동했다고 출력
③	dohanoi(n-1, start, tmp, end)	위 n-1개 원판을 start→tmp로 (end를 경유지로 활용)
④	print(start, end)	제일 큰 원판을 start→end로 직접 이동
⑤	dohanoi(n-1, tmp, end, start)	tmp에 있는 n-1개를 tmp→end로 (start를 경유지로 활용)
⑥	2 ** n - 1	이동 횟수. N≤100까지 파이썬 임의 정밀도 정수로 바로 계산 가능
⑦	if n <= 20	N이 크면 이동 횟수가 기하급수적으로 늘어 출력 불가. 20 이하만 경로 출력

⑦ 자주 하는 실수

실수 1: tmp와 end 인자를 헷갈림
dohanoi(n-1, start, tmp, end) 에서 세 번째 인자가 목적지(end 자리)이고, 네 번째가 경유지(tmp 자리)다.
함수 시그니처는 항상 (n, start, end, tmp) 순서임을 기억하자.

실수 2: 이동 횟수를 int로 계산하려다 오버플로우
다른 언어에서는 2^100이 long long 범위를 훨씬 초과한다. 파이썬은 괜찮지만, Java/C++ 풀이 시에는 BigInteger를 써야 한다.

🎯 핵심 정리

• N개를 옮기는 문제 = N-1개를 두 번 옮기는 문제로 분해
• 재귀 구조: dohanoi(n-1, start, tmp, end) → 이동 → dohanoi(n-1, tmp, end, start)
• 이동 횟수: T(N) = 2·T(N-1) + 1 = 2ⁿ - 1
• N > 20이면 경로 출력 생략 (이동 횟수만 출력)
• 파이썬은 임의 정밀도 정수라 2 ** n - 1 그대로 써도 됨

· · ·

# 크래프톤정글 # 재귀 # 하노이탑 # 백준1914 # 골드5 # Python