[백준] 11729번 하노이 탑

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

재귀 문제중에 제일 많이 풀어본 문제가 아마 이 문제일 것 같다.

개인적으로 재귀라는 알고리즘 방식이 항상 관념적으로는 이해가 되는데 직관적으로 이해하기 어려운 느낌이 있다.

그렇다보니 알고리즘을 생각하는 과정에서 다른 방식보다 디버깅도 많이하게되고 결과를 보고 코드를 맞춰가는(?) 식으로 문제를 풀게 되는데 좋은 방향은 아닌 것 같아서 이 문제를 깊이있게 이해해보기로 했다.

(이쪽 분야에 있으신 분들은 이미 다 이해하고 있을 거란 생각이 들어서 꼭 해야겠다는 생각도 들었다.)

 

하노이의 탑 원리(출처:위키백과)

알고리즘 방식

위와 같이 4층짜리 탑이 있고 위에서부터 각 층에 해당하는 원판을 a, b, c, d라 하면 움직이는 원판의 순서는

a b a c a b a d a b a c a b a = 15(2^4 - 1)이다.

a b a c a b a 의 과정을 X라 했을 때 위의 과정은

X d X 로 표현할 수 있으며 이를 Y라 하자.

원판 5개(a, b, c, d, e)에 대한 원판의 순서는

X d X e X d X  = 31(2^5 - 1)이고 이는 다시 Y e Y로 표현할 수 있다.

(위의 과정은 원판이 2개일 때와 3개일 때도 통용된다.

1개일 때는 당연히 a = A

2개일 때는 a b a = A b A = B

3개일 때는 a b a c a b a = B c B = X 와 같다.)

 

이를 통해 몇 가지 규칙을 알 수 있는데

 1) 제일 큰 원판은 무조건 1 -> 3 으로 1번만 움직인다.

 2) 제일 큰 원판을 제외한 탑은 1->2 로 이동 후 1) 과정을 진행 후 다시 2->3 으로 이동한다.

 

이를 통해 하노이의 탑의 높이에 대한 이동횟수를 나타내는 함수 a(n)은

a(n) = a(n - 1) * 2 + 1임을 알 수 있다.

이를 통해 일반항을 유도하면

[ a(n) + 1 ] = 2 [ a(n - 1) + 1 ]   

[ a(n) + 1 ] = [ a(1) + 1 ] * 2^(n - 1) 이고 a(1) = 1이므로

a(n) = 2^n - 1이 나온다.

 

위의 과정 중에 설명을 빼먹은 것이 있는데, 탑 전체에 대하여

위치를 1 -> 3으로 옮기는 과정과 1 -> 2로 옮기는 과정의 이동횟수는 당연히 같다.

앞서 언급한 1번 규칙을 통해 제일 큰 원판은 단 한번 1 -> 3으로 이동하는 것을 안다.

그러기 위해 두번째로 큰 원판은 이전 과정에서 1 -> 2으로 이동되어 있어야 한다.

이는 곧 세번째로 큰 원판이 1 -> 3으로 이동되었어야함을 의미하고

위의 과정이 제일 위의 원판까지 반복됨을 알 수 있다.

 

이제 아래 코드를 통해 위의 방식이 어떻게 구현되는지를 이해해야 한다.

먼저 재귀함수에 해당하는 아래 함수의 인자의 의미를 이해해야한다.

void hanoi(int n, int from, int by, int to) {

n - 원판의 개수

from - 탑의 현재 위치

by - 탑을 옮기기 위해 사용되는 위치

      (제거하고 구현하는 코드도 많다. 하지만 이해하기에는 이코드가 제일 좋은 것 같다.)

to - 탑을 옮기려는 위치

 

위의 인자들을 머리에 기억하고 n = 3일때 함수 내부의 과정을 나열해보면

hanoi(3, 1, 2, 3)

  hanoi(2, 1, 3, 2)
    hanoi(1, 1, 2, 3)
      화면 출력 : 1 - > 3
	화면 출력 : 1 -> 2
	hanoi(1, 3, 1, 2)
	  화면 출력 : 3 -> 2
  화면 출력 : 1 -> 3
  hanoi(2, 2, 1, 3)
	hanoi(1, 2, 3, 1)
	  화면 출력 : 2 - > 1
	화면 출력 : 2 -> 3
	hanoi(2, 1, 2, 3)
	  화면 출력 1 -> 3

처럼 된다.

위에서 설명했던 방식을 통해

제일 큰 원판을 제외한 탑을 다른 자리로 옮기는 과정을 X

제일 큰 원판을 O라고 하면 아래 함수내부에서 7번째줄 8번째줄 9번째줄이 순서대로 XOX를 나타냄을 알 수 있다.

이를 통해 모든 n에 대하여 아래 과정이 성립됨을 알 수 있다.

void hanoi(int n, int from, int by, int to) {
	if (n == 1) {
		cout << from << ' ' << to << '\n';
		return;
	}
	
	hanoi(n - 1, from, to, by);         // X
	cout << from << ' ' << to << '\n';  // O
	hanoi(n - 1, by, from, to);         // X
}

 

소스코드

#include <iostream>
#include <math.h>

using namespace std;

void hanoi(int n, int from, int by, int to) {
	if (n == 1) {
		cout << from << ' ' << to << '\n';
		return;
	}
	
	hanoi(n - 1, from, to, by);
	cout << from << ' ' << to << '\n';
	hanoi(n - 1, by, from, to);
}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	int K, A, B;

	cin >> N;

	K = pow(2, N) - 1;
	cout << K << '\n';

	hanoi(N, 1, 2, 3);

	return 0;
}