[BaekJoon] 11729번 - 하노이 탑 이동 순서 [Java][C++]

문제 링크

---

1. 아이디어

재귀를 처음 배울 때 자주 나오는 유명한 하노이 탑 문제로 이동 횟수와 순서를 출력해야 한다. 하노이 탑은 1번에서 3번으로 모든 원판을 이동하기 위해 가장 아래 원판을 제외한 나머지 원판들을 2번으로 옮긴 후 가장 아래 원판을 3번으로 옮기고 다시 2번으로 옮긴 원판들을 3번으로 옮기면 된다. 이때 현재 하노이 탑을 N개의 원판을 옮기는 문제라 했을 때, 1번에서 2번으로 원판을 옮기는 것은 N-1개의 원판을 옮기는 문제와 동일하게 된다. 따라서 1번 위치를 from, 2번 위치를 by, 3번 위치를 to로 재귀 함수를 수행하며 재귀는 from에서 to를 활용해 by로 N-1개의 원판을 옮기고, 가장 아래 원판을 from에서 to로 옮긴 후 다시 by에서 from을 활용해 to로 N-1개의 원판을 옮기면 된다. 세 개의 장대는 각각 출발지나 목적지, 또는 경유지 세 가지 역할 중 하나를 한다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static StringBuilder sb = new StringBuilder();
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        dfs(n, 1, 2, 3);
        System.out.println(cnt);
        System.out.println(sb);
    }

    static void dfs(int n, int from, int by, int to) {
        if (n == 0) return;

        dfs(n - 1, from, to, by);

        sb.append(from).append(" ").append(to).append("\n");
        cnt++;

        dfs(n - 1, by, from, to);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

string ans;
int cnt = 0;

void dfs(int n, int from, int by, int to) {
    if (n == 0) return;

    dfs(n - 1, from, to, by);

    ans += to_string(from) + " " + to_string(to) + '\n';
    cnt++;

    dfs(n - 1, by, from, to);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    dfs(n, 1, 2, 3);

    cout << cnt << '\n';
    cout << ans << '\n';
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---