[C] 하노이탑(the tower of hanoi) 재귀

하노이탑 문제

막대 A, B, C가 있고 막대 A에 아래에서부터 크기가 큰 순서대로 원판이 쌓여있다. 막대 A의 원판들을 막대 C에 옮겨야한다.

이 때 지켜야할 3가지 조건이 있다.

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

원판이 3개일 경우 A에서 C로 이동하는 과정을 그림으로 그리면 다음과 같다.

원판의 개수가 n개라고 할 경우, 다음과 같이 단순하게 생각할 수 있다.

A에 쌓여있는 위에서부터 n-1개의 원판을 B에 이동하고, 제일 밑에 있는 하나의 원판을 C로 옮긴다. 그리고 다음으로 B에 있던 n-1개의 원판을 C로 옮긴다.

 

 

이를 순환 알고리즘으로 나타내면

 

#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(3, 'A', 'B', 'C');
	return 0;
}

 

여기서 hanoi(3, A, B, C)를 호출하면 hanoi(2, A, C, B), printf("원판 3을 A에서 C로 옮긴다), hanoi(2, B, A, C)가 호출된다. 즉, 그림에서와 같이 hanoi(2, A, C, B)에서 from이 A to가 B가 되어 2개의 원판을 A에서 B로 옮기고, 원판 3을 A에서 C로 옮기고,  hanoi(2, B, A, C)에서 from이 B to가 C가 되어 2개의 원판을 B에서 C로 옮긴다는 의미가 된다.

 

위 프로그램을 실행하면 다음과 같다. 

 

원판이 3개일 경우에 이 프로그램을 실행했을 때의 함수 호출 과정은 다음 그림과 같다.