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

백준의 하노이 탑 이동순서(11729) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

하노이 탑을 쌓는 과정을 찾는 문제이다. 구체적으로는 세 개의 장대가 있을 때, 1번 장대에 있는 원판들을 규칙에 맞게 옮기면서 모두 3번 장대로 옮겨야 한다.

하노이 탑을 옮기는 과정을 간단하게 알아보자. 예를들어서 원판이 3개가 존재한다고 가정해보자.

1번원판이 가장작고, 3번 원판이 가장 큰 원판이다.

하노이 탑을 이동시키는 과정은 다음과 같다.

1. 3개의 원판 중, 2개의 원판을 2번 장대로 옮긴다.

2. 나머지 한 개의 원판을 3번 원판으로 옮긴다.

3. 2번 장대에 있는 2개의 원판을 다시 3번 장대로 옮긴다.

과정을 쓰면 위와 같이 적을 수 있다. 물론 그 과정에서 '중간다리 역할을 하는 장대'가 반드시 필요하다.

1번과정을 예로 들어보면 2개의 원판을 2번 장대로 옮겨야 할 때, 상대적으로 더 큰 원판이 작은 원판 위로 올라갈 수 없기 때문에

1번원판 → 3번장대, 2번원판 → 2번장대, 1번원판 → 2번원판

이런식으로 옮겨주어야 한다. 여기서 '2번장대'와 같이 중간다리 역할을 하는 장대가 필요하다.

본인은 재귀를 통해서 하노이 탑을 이동시켜 주었다.

재귀에서 사용한 변수는 4개가 있다. (현재 원판의 갯수 , 시작 장대번호, 중간다리 역할의 장대번호 , 도착 장대번호)

즉, 가장 초기 상태의 호출은 (N , 1 , 2 , 3) 으로 호출될 것이다.

왜냐하면, N개의 원판이 1번 장대에서 시작해서, 2번 장대를 중간다리 역할 삼아, 3번장대로 가야하기 때문이다.

그 이후에는 위에서 말한 과정들을 재귀로 만들어 주었다.

N - 1개의 원판들을 2번 장대로 옮기는 과정과 나머지 한개의 원판을 3번과정으로 옮기는 과정, 그리고 최종적으로 2번장대에

있는 N - 1개의 원판들을 다시 3번 장대로 옮기는 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
using namespace std;
 
int N;
vector<pair<int, int>> Answer;
 
void Input()
{
    cin >> N;
}
 
void Hanoi(int Num, int Start, int Mid, int End)
{
    if (Num == 1)
    {
        Answer.push_back(make_pair(Start, End));
        return;
    }
 
    Hanoi(Num - 1, Start, End, Mid);
    Answer.push_back(make_pair(Start, End));
    Hanoi(Num - 1, Mid, Start, End);
}
 
void Solution()
{
    Hanoi(N, 1, 2, 3);
    cout << Answer.size() << endl;
    for (int i = 0; i < Answer.size(); i++)
    {
        cout << Answer[i].first << " " << Answer[i].second << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}