[BOJ] 하노이 탑 이동 순서(11729)

[백준(BOJ)] 11729_하노이 탑 이동 순서 C++

문제 : BOJ_11729번 하노이 탑 이동 순서

문제 설명

재귀

재귀 문제로 유명한 하노이 탑 문제입니다.

n을 입력받으면 세 개의 장대 중 첫 번째 장대에 n 개의 탑이 쌓이는 것으로 시작합니다.

n 개의 탑은 가장 위에 있는 원판이 가장 가볍고 아래로 갈수록 무거운 원판이며, 가벼운 원판 위에 무거운 원판이 올라갈 수 없습니다.

각 장대 중 가장 위에 있는 원판을 하나 옮기는 것을 1회로 할 때, 최초에 첫 번째 장대에 있었던 원판을 모두 세 번째 원판으로 옮기는 최소 이동 회수를 구하는 것이 문제입니다.

---

Solution

현재 장대의 위치를 st, 이동해야 하는 장대의 위치를 ed, 나머지 장대를 mid라고 합시다.

처음에 n을 3이라고 입력하면 첫 번째 장대에 3개의 원판이 놓여 있는 상황이 되고, 이 원판을 모두 3번째 원판에 옮겨야 합니다.

가장 무거운 3번째 원판을 3번째 장대에 옮기려면 3번째 원판에 있는 모든 원판을 다른 장대로 이동시켜야 하고, 3번째 장대는 비어있어야 합니다.

즉, 3번째 원판 위에는 아무것도 없는 상태 + 나머지 원판은 모두 2번으로 옮겨진 상태를 충족하면 3번째 원판을 3번 장대로 옮길 수 있고, 3번째 원판을 3번 장대로 옮긴 뒤 2번 장대에 있던 모든 원판을 다시 3번 장대로 옮겨야 합니다.

이를 재귀적인 상황으로 다시 정리하면,

• 가장 무거운 원판을 제외한 n-1개의 원판을 mid로 옮김
• 가장 무거운 원판을 ed로 옮김
• 첫 번째 과정에서 옮겼던 n-1개의 원판을 ed로 옮김

이를 재귀로 코드를 짜면 문제를 해결할 수 있습니다.

---

Description

• 전체 옮긴 횟수를 출력하고 옮겨진 원판의 내용을 출력해야 하므로, 각 원판의 이동경로를 queue<pair<int, int>> q에 담고, q.size()를 출력한 뒤 q의 내용을 출력했습니다.
• 첫 번째 장대의 위치를 1, 두 번째는 2, 3번째는 3으로 잡으면 mid = 6 - st - ed가 됩니다.
• 재귀의 기저 조건은 현재 원판 번호가 1일 때 가장 가벼운 원판이므로 이 상황에선 바로 ed로 이동해 주고 이를 큐에 담고 재귀를 종료합니다.

---

#include <iostream>
#include <queue>
using namespace std;
queue <pair<int,int>> q;
void recursion(int idx, int st, int ed);
int main() {
    int n;
    cin >> n;
    recursion(n, 1, 3);
    cout << q.size() << '\n';
    while (!q.empty()) {
        cout << q.front().first << ' ' << q.front().second << '\n';
        q.pop();
    }
    return 0;
}
void recursion(int idx, int st, int ed){
    if(idx==1){
        q.push({st,ed});
        return;
    }
    int mid = 6-st-ed;
    recursion(idx-1,st,mid);
    q.push({st,ed});
    recursion(idx-1,mid,ed);
}