백준 11729 - 하노이 탑 이동 순서

문제

 

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

11729번: 하노이 탑 이동 순서

 

 

풀이

 

하노이 탑의 이동 순서를 구현하는 문제이다. 하노이 탑 알고리즘은 다음과 같다.

 

1. a b c 막대가 있고 a에 n개의 원판이 꽃혀져 있다면 n-1개의 원판을 b로 옮긴다.

2. a에 있는 1개의 막대를 c로 옮긴다.

3. b에 있는 n-1개의 막대를 c로 옮긴다.

 

위 과정을 한번에 진행할 수 없으므로 재귀함수를 통해 여러번 진행하게 된다.  

 

 

코드

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int K, cnt;
vector<pair<int, int>> v;
 
void hanoi(int n, int from, int to, int by)
{
    cnt++;
    if (n == 1)
    {
        v.push_back({ from , to });
    }
    else
    {
        hanoi(n - 1, from, by, to);
        v.push_back({ from, to });
        hanoi(n - 1, by, to, from);
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> K;
    hanoi(K, 1, 3, 2);
 
    cout << cnt << '\n';
    for (int i = 0; i < v.size(); i++)
        cout << v[i].first << ' ' << v[i].second << '\n';
 
    return 0;
}