[백준] 11729: 하노이 탑 이동 순서 — 재귀 풀이 (Java)

하노이 탑 이동 순서

백준 11729 Silver I 재귀 · 분할정복

⏱️ 읽기 시간: 약 5분

📑 목차

• 1. 문제 분석
• 2. 접근법
• 3. 풀이 (Java)
• 4. 예제 트레이스
• 5. 복잡도 분석
• 6. 클린 코드

문제 분석

• 세 개의 장대에서 N개의 원판을 1번 → 3번 장대로 옮겨야 한다.
• 한 번에 한 개의 원판만 이동 가능하며, 큰 원판 위에 작은 원판만 올릴 수 있다.
• 최소 이동 횟수와 이동 과정을 모두 출력해야 한다.
• N ≤ 20이므로 최대 2²⁰ - 1 = 1,048,575번 이동.

접근법

재귀 (분할정복) — 하노이 탑의 핵심 아이디어는 단 3단계로 요약된다:

hanoi(n, from, to, via) = n개 원판을 from → to로 이동 (via를 보조로 사용)

1. 위 n-1개를 from → via로 이동 (보조: to)
2. 맨 아래 1개를 from → to로 이동
3. n-1개를 via → to로 이동 (보조: from)

이동 횟수는 T(n) = 2·T(n-1) + 1이므로 2^N - 1로 확정된다.

출력량이 최대 100만 줄이므로 StringBuilder로 모아서 한 번에 출력하는 것이 핵심.

풀이 (Java)

import java.io.*;

public class Main {
    static StringBuilder sb = new StringBuilder();

    // n개 원판을 from → to로 이동 (via를 보조 장대로 사용)
    static void hanoi(int n, int from, int to, int via) {
        if (n == 0) return;
        hanoi(n - 1, from, via, to);   // 위 n-1개를 보조 장대로
        sb.append(from).append(' ').append(to).append('\n'); // 맨 아래 원판 이동
        hanoi(n - 1, via, to, from);   // n-1개를 목적지로
    }

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(
            new BufferedReader(new InputStreamReader(System.in)).readLine().trim()
        );
        sb.append((1 << N) - 1).append('\n'); // 이동 횟수 = 2^N - 1
        hanoi(N, 1, 3, 2);
        System.out.print(sb);
    }
}

예제 트레이스

N = 3,  hanoi(3, 1, 3, 2)

hanoi(3, 1→3, via 2)
├─ hanoi(2, 1→2, via 3)
│   ├─ hanoi(1, 1→3, via 2) → 출력: "1 3"
│   ├─ 출력: "1 2"
│   └─ hanoi(1, 3→2, via 1) → 출력: "3 2"
├─ 출력: "1 3"
└─ hanoi(2, 2→3, via 1)
    ├─ hanoi(1, 2→1, via 3) → 출력: "2 1"
    ├─ 출력: "2 3"
    └─ hanoi(1, 1→3, via 2) → 출력: "1 3"

최종 출력:
7
1 3 / 1 2 / 3 2 / 1 3 / 2 1 / 2 3 / 1 3  ✅

시간 복잡도

O(2^N)

공간 복잡도

O(2^N)

클린 코드 — Java

import java.io.*;

public class Main {
    static StringBuilder sb = new StringBuilder();

    static void hanoi(int n, int from, int to, int via) {
        if (n == 0) return;
        hanoi(n - 1, from, via, to);
        sb.append(from).append(' ').append(to).append('\n');
        hanoi(n - 1, via, to, from);
    }

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine().trim());
        sb.append((1 << N) - 1).append('\n');
        hanoi(N, 1, 3, 2);
        System.out.print(sb);
    }
}