(C++) 백준 11729번 - 하노이 탑 이동 순서

문제 링크 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

풀이

재귀 문제의 대명사격인 하노이 탑 문제이다.

s에서 l로 n개를 이동하려면 다음과 같은 과정을 거치면 된다.

1. 제일 아래에 있는 가장 큰 판을 제외한 n-1개의 판을 s에서 6-s-l로 이동시킨다.

2. 제일 큰 판을 s에서 l로 이동시킨다.

3. 1에서 6-s-l로 이동한 n-1개의 판을 l로 이동시킨다. 

이 과정을 재귀로 반복하여 문제를 풀이하였다.

#include <iostream>

using namespace std;

void hanoi(int s, int l, int n){ // s에서 l로 n개를 이동하려면
    if(n == 1){ // 하나가 남으면 이동하고 이를 출력
        cout << s << " " << l << "\n";
        return;
    }
    hanoi(s, 6-s-l, n-1); // 제일 큰 판을 제외한 n-1개를 s에서 6-s-l로 이동하고
    cout << s << " " << l << "\n"; // 제일 큰 판을 s에서 l로 이동하고
    hanoi(6-s-l, l, n-1); // n-1개를 6-s-l에서 l로 이동
}

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

    int n;
    cin >> n;
    cout << (1<<n)-1 << "\n"; // 판의 개수가 k일 때 2^k-1번 이동
    hanoi(1, 3, n);
}