[C/자료구조] 하노이탑 문제

하노이탑이란?

퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

하노이탑

하노이탑의 조건

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 맨 위에 있는 원판만 이동할 수 있다.
3. 크기가 작은 원판위에 큰 원판이 쌓일 수 없다.
4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.

이제 문제 자체는 이해했으니, 이를 체계적으로 정의해보자. "체계적"이라함은, 문제의 입력과 출력을 보다 함수에 가깝게 정의하자는 것이다. 우리는 "원반의 이동횟수를 최소화하고자 할 때, 각 원반을 옮기는 모든 순서를 출력하는 것"으로 한다. 이때 각 이동의 출력은 '3번 원반을 A에서 C와 같이로 정하며, 입력은 원반의 개수로 받는다.

이를 구현하는 함수 hanoi를 대략적으로 정의하면 다음과 같다.

hanoi(N): 원반의 개수 N을 입력 받아 모든 원반을 "C" 막대에 옮기는 각 움직임을 출력한다.

하노이탑은 순환적으로 생각하면 쉽게 해결할 수 있다. 순환이 일어날수록 문제의 크기가 작아져야 한다. 여기서의 문제는 크기는 이동하여야 하는 디스크의 개수가 된다. 다음과 같이 문제를 나누어 생각하여 보자. n개의 원판이 A에 쌓여있는 경우, 먼저 위에 쌓여 있는 n-1개의 원판을 B로 옮긴 다음, 제일 밑에 있는 원판을 C로 옮긴다. 이어서 B에 있던 n-1개의 원판을 C로 옮긴다. 자 이제 문제는 B에 쌓여있던 n-1개의 원판을 어떻게 C로 옮기느냐이다. 이 문제를 다음과 같이 알고리즘을 만들어서 생각하여 보자.

void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) {
		from에 있는 한 개의 원판을 to로 옮긴다.
	}
	else {
		1. from의 맨 밑의 원판을 제외한 나머지 원판들을 tmp로 옮긴다.
		2. from에 있는 한 개의 원판을 to로 옮긴다.
		3. tmp의 원판들을 to로 옮긴다.
	}
}

이러한 알고리즘으로 프로그램을 작성하여 보면

#include <stdio.h>

void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) {
		printf("원판 1을 %c에서 %c으로 옮긴다.\n", from, to);
	}
	else {
		hanoi_tower(n - 1, from, to, tmp);
		printf("원판 %d을 %c에서 %c으로 옮긴다.\n", n, from, to);
		hanoi_tower(n - 1, tmp, from, to);
	}
}

int main(void) {
	hanoi_tower(4, 'A', 'B', 'C');

	return 0;
}

원판을 이동한다는 것은 그냥 화면에 어디서 어디로 이동한다고 출력해주면 된다. 

위 프로그램을 실행시켜보면

위와 같은 프로그램 출력이 결과로 나오게된다.

 

이번 글을 통해 순환의 파워를 가장 극명하게 보여주는 예제인 하노이탑 문제를 해결해보았다.