[프로그래머스] 하노이의 탑(Java) — 재귀

📌 핵심 요약

• 재귀 구조 — n개 문제는 “n-1개 치우기 → 가장 큰 원판 옮기기 → n-1개 다시 옮기기” 3단계로 강제된다
• 역할 교대 — 재귀 호출마다 목적지(to)와 보조 기둥(via)이 서로 뒤바뀐다. 인자 순서가 핵심
• 이동 횟수 — 이동횟수(n) = 2 × 이동횟수(n-1) + 1, 따라서 총 2ⁿ-1회

 

목차

1 문제 소개

Programmers #12946

하노이의 탑

n ≤ 15 · 원판은 큰 것 위에 작은 것만

난이도: Level 2

n개의 원판을 1번 기둥에서 3번 기둥으로 옮기는 최소 이동 순서를 [from, to] 쌍의 배열로 반환하는 문제다. 한 번에 한 개의 원판만 옮길 수 있고, 큰 원판을 작은 원판 위에 올릴 수 없다.

풀이 과정

1. 가장 큰 원판을 옮기려면 위의 n-1개가 먼저 보조 기둥으로 비켜나 있어야 한다는 점에서 재귀 구조를 발견한다.
2. “n-1개 치우기 → 가장 큰 원판 이동 → n-1개 다시 옮기기” 3단계로 함수를 구성한다.
3. 재귀 호출 시 목적지와 보조 기둥의 역할을 교대하며 인자를 넘긴다.
4. 총 이동 횟수가 2ⁿ-1로 확정되므로 결과 배열 크기를 미리 할당하고, index를 증가시키며 기록한다.

2 접근 — 왜 n-1로 쪼개지는가

이 문제의 핵심 질문은 하나다. “n개의 원판을 옮기려면, 그 전에 무엇이 반드시 일어나야 하는가?”

가장 큰 원판(n번)을 1번 기둥에서 3번 기둥으로 옮기는 순간을 생각해보면, 필요한 조건은 두 가지다.

첫째, 큰 원판 위에 아무것도 없어야 하므로 위에 쌓인 n-1개가 전부 보조 기둥에 가 있어야 한다.

둘째, 목적지에 더 작은 원판이 있으면 그 위에 올릴 수 없으므로 목적지가 비어 있어야 한다. 이 두 조건 때문에 전체 과정이 강제로 3단계가 된다.

 

하노이 3단계 구조

① 위의 n-1개를 보조 기둥으로 치운다     → hanoi(n-1, from, via, to)
② 가장 큰 원판 1개를 목적지로 옮긴다    → answer에 {from, to} 기록
③ 치워둔 n-1개를 목적지로 다시 옮긴다   → hanoi(n-1, via, to, from)

여기서 관점 전환이 중요하다. ①의 “n-1개를 보조 기둥으로 치운다”는 것 자체가 똑같은 하노이 문제다.

원판이 n-1개이고 목적지가 via일 뿐이다. 그래서 같은 함수를 다시 호출하고, 그 안에서 또 n-2개짜리 문제로 쪼개지며, 결국 그냥 옮기면 되는 n == 1까지 내려가서 멈춘다.

n-1로 감소하는 이유는 가장 큰 원판 하나를 처리하고 나면 남는 것이 정확히 원판 n-1개짜리 동일한 문제이기 때문이다.

n = 3 예시

 

trace — hanoi(3, 1→3, via 2)

hanoi(3, 1→3, via 2)
├─ hanoi(2, 1→2, via 3)      "위 2개를 2번으로 치우기"
│  ├─ hanoi(1, 1→3)          → [1,3]  원판1을 3번에 잠시 대피
│  ├─ 원판2 이동              → [1,2]
│  └─ hanoi(1, 3→2)          → [3,2]  대피시킨 원판1을 원판2 위로
├─ 원판3 이동                 → [1,3]  ★ 가장 큰 원판
└─ hanoi(2, 2→3, via 1)      "치워둔 2개를 3번으로"
   ├─ hanoi(1, 2→1)          → [2,1]
   ├─ 원판2 이동              → [2,3]
   └─ hanoi(1, 1→3)          → [1,3]

결과는 [1,3] [1,2] [3,2] [1,3] [2,1] [2,3] [1,3]으로 총 7회(2³-1)다. 트레이스에서 보이듯 각 단계에서 to와 via가 계속 뒤바뀐다. n-1개를 치울 때는 원래 보조 기둥이 임시 목적지가 되고, 원래 목적지가 보조 역할을 한다.

ℹ️

이동 횟수의 점화식

이동횟수(n) = 이동횟수(n-1) + 1 + 이동횟수(n-1) = 2 × 이동횟수(n-1) + 1. 이를 풀면 총 이동 횟수는 2ⁿ-1이 된다. 앞서 정리한 가장 큰 정사각형 문제의 점화식이 “이웃 칸의 답으로 현재 답 만들기”였다면, 하노이는 “한 단계 작은 문제의 답으로 현재 답 만들기”다.

3 전체 코드

 

Java — Solution.java

class Solution {
    private int index = 0;

    public int[][] solution(int n) {
        int[][] answer = new int[(1 << n) - 1][2]; // 2^n - 1

        hanoi(n, 1, 3, 2, answer);

        return answer;
    }

    // from: 최초 기둥, to: 목적지 기둥, via: 보조 기둥
    private void hanoi(int n, int from, int to, int via, int[][] answer) {
        if (n == 1) {
            answer[index++] = new int[]{from, to};
            return;
        }

        hanoi(n - 1, from, via, to, answer);   // ① 위의 n-1개를 보조 기둥으로
        answer[index++] = new int[]{from, to}; // ② 가장 큰 원판 이동
        hanoi(n - 1, via, to, from, answer);   // ③ 치워둔 n-1개를 목적지로
    }
}

총 이동 횟수가 2ⁿ-1로 확정되어 있으므로 결과 배열을 미리 할당했고, 재귀가 진행되는 순서 그대로 index++로 기록했다. 함수 본문이 3단계 구조와 정확히 1:1로 대응하도록 유지했다.

💡

인자 순서가 곧 역할 교대

①에서는 (from, via, to), ③에서는 (via, to, from)으로 두 번째·세 번째 인자가 바뀐다. n-1개를 치울 때는 보조 기둥이 임시 목적지가 되고, 다시 옮길 때는 보조 기둥이 출발점이 되는 역할 교대가 인자 순서에 그대로 담겨 있다. 하노이 구현의 전부가 이 두 줄이다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.