BOJ 11729 - 하노이 탑 이동 순서

문제 링크

문제#

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

• 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
• 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력#

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력#

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

풀이#

원반 n개를 옮기려면 먼저 n-1개를 보조 기둥으로 옮기고, 가장 큰 원반 하나를 목적지로 보낸 뒤, 다시 n-1개를 목적지로 옮겨야 한다. 이 구조가 그대로 재귀 정의가 된다.

즉 solve(n, from, via, to)는 solve(n-1, from, to, via), 큰 원반 이동, solve(n-1, via, from, to) 순서로 이루어진다. 이동 횟수는 $2^n - 1$이다.

큰 원반은 언제나 한 번만 움직이고, 나머지는 같은 문제가 반복된다.

코드#

#include <iostream>
using namespace std;
 
// 기둥을 각각 1, 2, 3으로 지정, ex) x = 1, y = 3, 남은 기둥: 2
// x : 원반이 있는 기둥, y : 원반을 옮길 기둥, 6-x-y : 남은 기둥
// n : 원반 번호 ex) 1, 2, ..., n-1, n
void hanoi(int n, int x, int y) {
 
	if(n == 1) // 가장 위에 있는 원반을 옮기는 경우
		cout << x << " " << y << '\n';
	else { // 가장 아래의 원반을 제외한 나머지 원반을 옮기는 경우
		hanoi(n - 1, x, 6-x-y); 
		cout << x << " " << y << '\n';
		hanoi(n - 1, 6-x-y, y);
	}
	
}
 
void solve() {
	
	int n;
	cin >> n;
 
	//하노이 탑의 총 이동 횟수는 2^n - 1, 시프트 연산으로 표현
	cout << (1 << n) - 1 << '\n';
 
	hanoi(n, 1, 3);
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 출력 횟수 기준 $O(2^N)$
• 공간 복잡도: 재귀 호출 스택 기준 $O(N)$

마무리#

하노이 탑은 큰 문제를 같은 작은 문제 두 개로 나누는 재귀의 전형적인 예시다. 가장 큰 원반 하나를 기준으로 앞뒤가 대칭이다.