[백준 - 11729] 하노이 탑 이동 순서 - C++

분류: 재귀 /

 

문제

문제 링크

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

풀이

#include <iostream>
#include <vector>
using namespace std;

struct e {int from, to;};
vector<e> v;

void move(int n, int from, int to) {
    if(n == 1) {
        v.push_back({from, to});
        return;
    }
    int tmp = 6-from-to;
    move(n-1, from, tmp);
    v.push_back({from, to});
    move(n-1, tmp, to);
}

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

    int N; cin >> N;
    move(N, 1, 3);
    cout << v.size() << '\n';
    for(const auto &x:v) 
        cout << x.from << ' ' << x.to << '\n';
}

재귀함수의 귀납적 수도 코드

• n = 1 일때 `from` -> `to` 옮기면 된다.
• n = k-1 일때 `from`에서 `to`로 옮기는 방법을 안다면 n = k일때 옮기는 방법은 다음과 같다.
  • `move(n-1, from, tmp)` -> `move(1, from, to)`-> `move(n-1, tmp, to)`

 

벡터를 사용하지 않고 이동 횟수를 미리 계산한 뒤 `push_back`대신 바로 출력해도 된다.

원판 k개를 이동하기 위해 t번 이동했다고 하면 k+1개의 원판을 이동하기 위해서는 2t+1번의 이동이 필요하다.

$$\text{when, }a_k=t, a_{k+1}=2t+1\\[0.75em]\begin{align*}&&a_{k+1}&=2a_k+1\\[0.25em]&-&a_k&=2a_{k-1}+1\\[0.25em]\hline&&a_{k+1}-a_k&=2(a_k-a_{k-1})\quad(k>1)\end{align*}\\[1em]\text{let, }b_k=a_{k+1}-a_k\\[0.75em]b_k=2b_{k-1},\quad b_1=2\\[0.25em]\therefore b_n=2^n\\[1em]a_{k+1}-a_k=2^k,\quad a_1=1\\[0.25em]\begin{align*}a_n&=2^{n-1}+a_{n-1}\\[0.25em]a_n&=2^{n-1}+2^{n-2}+a_{n-2}\\[0.25em]a_n&=2^{n-1}+2^{n-2}+2^{n-3}+a_{n-3}\\&\vdots\\a_n&=\sum_{i=1}^{n-1}{2^i}+1\\[0.25em]a_n&=2^n-2+1=2^n-1\end{align*}$$

위 증명을 이용해 벡터에 따로 저장하지 않고 이동 횟수를 계산해 출력하고 이동마다 바로 출력하면 다음과 같다.

#include <iostream>
using namespace std;

void move(int n, int from, int to) {
    if(n == 0) return;
    int nxt = n-1, tmp = 6-from-to;
    move(nxt, from, tmp);
    cout << from << ' ' << to << '\n';
    move(nxt, tmp, to);
}

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

    int N; cin >> N;
    cout << (1 << N) - 1 << '\n';
    move(N, 1, 3);
}