BOJ 11729 : 하노이 탑 이동 순서 [C++]

 

 

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

11729번: 하노이 탑 이동 순서

 

문제 요약

높이가 $N$인 하노이 탑을 푸는 데 걸리는 최소 이동 횟수와 이동 경로를 출력하는 문제이다.

 

해결 전략

높이가 $N$인 하노이 탑을 1번에서 3번으로 이동하는 것이 문제의 목표이다.

 

단순하게 생각해보자.

$N = 3$인 하노이 탑이 있고, 이를 3번 판 위로 모두 옮겨야 한다.

가장 밑 발판을 제외한 $N = 2$의 하노이 탑을 2번 판으로 옮긴다.

(이것은 한 번의 이동으로는 할 수 없지만, 큰 틀을 구상하기 위한 것이기 때문에 넘어가자.)

[ 1 단계 ]

가장 밑 발판을 3번 판으로 옮긴다.

[ 2 단계 ]

아까 옮겼던 $N = 2$ 탑을 3번 판으로 옮긴다.

[ 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);
}