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

문제

https://www.acmicpc.net/problem/11729

---

문제 요약

3개의 장대가 있고, 첫 번째 장대에 반경이 서로 다른 n개의 원판이 큰 순서대로 쌓여 있다.

 

다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮겨야 한다.

 

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

 

작업을 수행하는 데 필요한 이동 횟수와 순서를 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;

// {a, b} : a번째 탑의 가장 위 원판을 b번째 탑의 가장 위로 이동
vector<pair<int, int >> res;

// a번째 탑에서 cnt - 1개 원판을 b번째 탑으로 이동시켜두고, c번째 탑으로 옮기기
void move(int a, int b, int c, int cnt) {
    if (cnt == 1) {
        res.push_back(make_pair(a, c));
        return;
    }

    move(a, c, b, cnt - 1);
    move(a, 0, c, 1);
    move(b, a, c, cnt - 1);
}

int main() {
    cin >> n;

    move(1, 2, 3, n);

    cout << res.size() << "\n";

    for (int i = 0; i < res.size(); i++) {
        cout << res[i].first << " ";
        cout << res[i].second << "\n";
    }
}

---

코드 설명

하노이 탑은 재귀적으로 해결할 수 있다.

 

a번째 장대에서 c번 장대로 n개의 원판을 이동시키는 과정은 다음과 같다.

 

1. a번째 장대에서 b번 장대로 먼저 n - 1개의 원판을 이동시킨다.

 

2. a번째 장대에서 c번 장대로 1개의 원판을 이동시킨다.

 

3. b번 장대로 옮겼던 n - 1개의 원판을 c번 장대로 이동시킨다.

---

고찰

처음에는 원판을 옮기는 모든 경우를 분기 처리했다.

 

< 초기 코드 >

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;

// {a, b} : a번째 탑의 가장 위 원판을 b번째 탑의 가장 위로 이동
vector<pair<int, int >> res;

// a번째 탑에서 cnt개 원판을 b번째 탑으로 이동
void dfs(int a, int b, int cnt) {
    if (cnt == 1) {
        res.push_back(make_pair(a, b));
        return;
    }

    if (a == 1) {
        if (b == 2) {
            dfs(a, 3, cnt - 1);
            dfs(a, b, 1);
            dfs(3, b, cnt - 1);
        }
        else if (b == 3) {
            dfs(a, 2, cnt - 1);
            dfs(a, b, 1);
            dfs(2, b, cnt - 1);
        }
    }
    else if (a == 2) {
        if (b == 1) {
            dfs(a, 3, cnt - 1);
            dfs(a, b, 1);
            dfs(3, b, cnt - 1);
        }
        else if (b == 3) {
            dfs(a, 1, cnt - 1);
            dfs(a, b, 1);
            dfs(1, b, cnt - 1);
        }
    }
    else if (a == 3) {
        if (b == 1) {
            dfs(a, 2, cnt - 1);
            dfs(a, b, 1);
            dfs(2, b, cnt - 1);
        }
        else if (b == 2) {
            dfs(a, 1, cnt - 1);
            dfs(a, b, 1);
            dfs(1, b, cnt - 1);
        }
    }
}

int main() {
    cin >> n;

    dfs(1, 3, n);

    cout << res.size() << "\n";

    for (int i = 0; i < res.size(); i++) {
        cout << res[i].first << " ";
        cout << res[i].second << "\n";
    }
}

 

생각해보니, n - 1개의 원판을 옮겨둘 막대를 dfs 함수의 인자로 받으면 된다는 생각이 들었다.