BOJ 11729 : 하노이 탑 이동 순서 [C++]
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
문제 요약
높이가 $N$인 하노이 탑을 푸는 데 걸리는 최소 이동 횟수와 이동 경로를 출력하는 문제이다.
해결 전략
높이가 $N$인 하노이 탑을 1번에서 3번으로 이동하는 것이 문제의 목표이다.
단순하게 생각해보자.
$N = 3$인 하노이 탑이 있고, 이를 3번 판 위로 모두 옮겨야 한다.
가장 밑 발판을 제외한 $N = 2$의 하노이 탑을 2번 판으로 옮긴다.
(이것은 한 번의 이동으로는 할 수 없지만, 큰 틀을 구상하기 위한 것이기 때문에 넘어가자.)
가장 밑 발판을 3번 판으로 옮긴다.
아까 옮겼던 $N = 2$ 탑을 3번 판으로 옮긴다.
각 단계를 일반화해보자.
$N \ge 2$인 $N$에 대하여,
현재 높이 $N$인 하노이 탑의 판 번호를 now, 탑이 도착해야 하는 판 번호를 dest라고 하자.
1 단계는 높이 $N - 1$의 탑을 now, dest가 아닌 다른 지점으로 옮기는 것이다. (이 지점을 other라고 하자.)
2 단계는 현재 now에 남아있는 판을 dest로 옮기는 것이다.
3 단계는 other로 옮겼던 $N - 1$의 탑을 dest로 옮기는 것이다.
$N = 1$인 경우에는 그냥 now를 dest로 옮겨주기만 하면 된다.
1, 3단계에서 $N - 1$의 탑을 옮기는 행위는, 이 탑에 대해 각 단계를 다시 수행하는 것과 같다.
이 것을 재귀를 활용하여 간단하게 구현할 수 있다.
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
void Hanoi(int n, int now, int dest) {
if (n == 1) {
cout << now << ' ' << dest << '\n';
return;
}
int other = 6 - (now + dest);
Hanoi(n - 1, now, other);
cout << now << ' ' << dest << '\n';
Hanoi(n - 1, other, dest);
}
int main() {
int N;
cin >> N;
cout << ((1 << N) - 1) << '\n';
Hanoi(N, 1, 3);
}