[BOJ] 11729. 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

하노이 탑 문제는 재귀 호출을 이용하여 풀 수 있는 대표적인 문제이다.

먼저 옮기는 횟수는 원판의 개수가 n 개라고 했을 때 2의n제곱-1 이므로 먼저 출력해주고 시작할 수 있다.

 

 

장대 세개가 각각 a, b, c  (각각 1, 2, 3)라고 했을 때, n개의 원판을 a에서 c로 옮기려고 한다.

규칙에 따라서 맨 밑에 있는 원판이 c에 가장 먼저 놓여야 하는데, 그러기 위해서는 맨 밑 원판을 제외한 나머지 n-1개의 원판을 다른 비어있는 장대(b)로 옮겨놓아야 한다. 그리고 맨 밑 원판을 c로 옮겼으면 아까 옮겨 놓았던 n-1개의 원판을 다시 c로 가져온다.

 

 

이 때, a에서 b로 옮겨진 n-1개의 원판들도 같은 규칙으로 옮길 것이기 때문에 위의 내용을 그대로 재귀 함수로 구현해주면 된다.

즉, n-1개의 원판을 a에서 b로 옮기려고 하는 경우에 대해서 새로 구해주는 것이다.

 

 

a는 1, b는 2라고 했을 때, c는 6 - a - b로 표현할 수 있다.

a + b + c = 6

(1 + 2 + 3) = 6

 

 

밑의 코드에서는 처음 넘겨지는 a는 1, b는 3이다. (첫 번째 장대에서 세 번째 장대로 옮길 것이므로)

#include<iostream>
using namespace std;
 
 
void hanoi(int n, int a, int b) {
    if (n == 0) return;
    
    hanoi(n - 1, a, 6 - a - b);
    printf("%d %d\n", a, b);
    hanoi(n - 1, 6 - a - b, b);
 
}
 
int main() {
    int n;
    cin >> n;
 
    cout << (1 << n) - 1 << '\n';
 
    hanoi(n, 1, 3);
 
    return 0;
}