Chapter 02. 하노이 타워 : The Tower of Hanoi

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이번에 소개하는 주제는 앞서 보인 예제들과 달리 재귀적으로 접근하지 않으면 해결이 쉽지 않은 문제입니다.

하노이 타워 문제는 재귀 함수를 대표한다고도 볼 수 있습니다. 혹시 하노이 타워가 무엇인지 모른다면 짧게 검색해보고 오길 권합니다. 하노이 타워에 대한 설명은 하지 않겠습니다.

 

하노이 타워 문제를 막연하게 생각하면 뭔가 복잡한 논리가 필요할 듯 보입니다. 하지만 하노이 타워 문제는 매우 매우 간단한 과정을 반복할 뿐입니다. 하노이 타워 문제를 풀기 위해서는 어찌 됐든 가장 아래쪽에 위치한 가장 큰 원반을 목표지점에 옮겨야 합니다. 그러기 위해서는 그 위의 모든 원반들을 중간 지점에 옮겨야 합니다. 하노이 타워를 옮기는 메커니즘은 다음과 같습니다.

1. 가장 큰 원반을 제외한 나머지 원반들을 중간지점으로 옮긴다.
2. 가장 큰 원반을 목표지점으로 옮긴다.
3. 나머지 원반들을 목표지점으로 옮긴다.

위 메커니즘을 따르면 원반 7개를 옮기는 문제는 곧 원반 6개를 옮기는 문제가 된다는 것을 눈치챌 수 있습니다. 위 메커니즘을 기억하고 이를 바탕으로 직접 하노이 타워 문제를 해결하는 재귀 함수를 구현해 봅니다.

 

다음은 제가 구현한 함수입니다. 

//main.c 소스 파일로 저장
#include <stdio.h>

int Hanoi(int count)    //count = 원반 개수
{
	if (count == 1) return 1;

	return Hanoi(count - 1) * 2 + 1;
}

int main(void)
{
	printf("원반 3개 하노이탑 운반 횟수 : %d\n", Hanoi(3));
	printf("원반 5개 하노이탑 운반 횟수 : %d\n", Hanoi(5));
	printf("원반 12개 하노이탑 운반 횟수 : %d\n", Hanoi(12));

	return 0;
}

/*
실행결과

원반 3개 하노이탑 운반 횟수 : 7
원반 5개 하노이탑 운반 횟수 : 31
원반 12개 하노이탑 운반 횟수 : 4095

*/

위 예제는 하노이 타워 문제의 원반 개수에 따른 최소한의 이동 횟수를 보여줍니다. 그런데 책을 보다보니 정확히 어떤 원반을 어디로 옮겼는지를 표시하는 알고리즘을 원하고 있습니다. 이에 다시 구현해 보겠습니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int Hanoi(int count, char current, char mid, char goal)    //count = 원반 개수
{
	if (count == 1)
	{
		printf("1번 원반을 %c에서 %c로 이동\n", current, goal);
		return 1;
	}

	int sum = 0;
	sum += Hanoi(count - 1, current, goal, mid);
	printf("%d번 원반을 %c에서 %c로 이동\n", count, current, goal);
	sum += 1; 
	sum += Hanoi(count - 1, mid, current, goal);

	return sum;
}

int main(void)
{
	printf("원반 4개 하노이탑 운반 횟수 : %d\n", Hanoi(4, 'A', 'B', 'C'));

	return 0;
}

/*
실행결과

1번 원반을 A에서 B로 이동
2번 원반을 A에서 C로 이동
1번 원반을 B에서 C로 이동
3번 원반을 A에서 B로 이동
1번 원반을 C에서 A로 이동
2번 원반을 C에서 B로 이동
1번 원반을 A에서 B로 이동
4번 원반을 A에서 C로 이동
1번 원반을 B에서 C로 이동
2번 원반을 B에서 A로 이동
1번 원반을 C에서 A로 이동
3번 원반을 B에서 C로 이동
1번 원반을 A에서 B로 이동
2번 원반을 A에서 C로 이동
1번 원반을 B에서 C로 이동
원반 4개 하노이탑 운반 횟수 : 15

*/

그리고 이건 코드를 작성하다보니 개인적인 호기심에 작성하게 된 코드입니다.

//main.c 소스 파일로 저장
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	char line;
	char* ptower;
	int count;
	int full;
} Harnoi;

int Hanoi(int count, Harnoi* A, Harnoi* B, Harnoi* C, Harnoi* current, Harnoi* mid, Harnoi* goal)    //count = 원반 개수
{
	if (count == 1)
	{
		printf("1번 원반을 %c에서 %c로 이동\n", current->line, goal->line);
		goal->count += 1;
		goal->ptower[goal->full - goal->count] = current->ptower[current->full - current->count];
		current->ptower[current->full - current->count] = ' ';
		current->count -= 1;

		int i;
		for (i = 0; i < A->full; i++)
		{
			printf("%c\t%c\t%c\n", A->ptower[i], B->ptower[i], C->ptower[i]);
		}
		printf("------------------------\n");
		return 1;
	}

	int sum = 0;
	sum += Hanoi(count - 1, A, B, C, current, goal, mid);
	printf("%d번 원반을 %c에서 %c로 이동\n", count, current->line, goal->line);
	goal->count += 1;
	goal->ptower[goal->full - goal->count] = current->ptower[current->full - current->count];
	current->ptower[current->full - current->count] = ' ';
	current->count -= 1;

	int i;
	for (i = 0; i < A->full; i++)
	{
		printf("%c\t%c\t%c\n", A->ptower[i], B->ptower[i], C->ptower[i]);
	}
	printf("------------------------\n");
	sum += 1; 
	sum += Hanoi(count - 1, A, B, C, mid, current, goal);

	return sum;
}

int main(void)
{
	char HarnoiA[] = { '1', '2', '3', '4' };
	int len = sizeof(HarnoiA) / sizeof(HarnoiA[0]);

	char* HarnoiB = (char*)malloc(len);
	char* HarnoiC = (char*)malloc(len);
	if (HarnoiB == NULL || HarnoiC == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}

	int i;
	for (i = 0; i < len; i++)
	{
		HarnoiB[i] = ' ';
		HarnoiC[i] = ' ';
	}

	Harnoi hA = { 'A', HarnoiA, len, len };
	Harnoi hB = { 'B', HarnoiB, 0, len };
	Harnoi hC = { 'C', HarnoiC, 0, len };

	printf("원반 %d개 하노이탑 운반 횟수 : %d\n", len, Hanoi(len, &hA, &hB, &hC, &hA, &hB, &hC));

	free(HarnoiB);
	free(HarnoiC);

	return 0;
}

/*
실행결과

1번 원반을 A에서 B로 이동

2
3
4       1
------------------------
2번 원반을 A에서 C로 이동


3
4       1       2
------------------------
1번 원반을 B에서 C로 이동


3               1
4               2
------------------------
3번 원반을 A에서 B로 이동


                1
4       3       2
------------------------
1번 원반을 C에서 A로 이동


1
4       3       2
------------------------
2번 원반을 C에서 B로 이동


1       2
4       3
------------------------
1번 원반을 A에서 B로 이동

        1
        2
4       3
------------------------
4번 원반을 A에서 C로 이동

        1
        2
        3       4
------------------------
1번 원반을 B에서 C로 이동


        2       1
        3       4
------------------------
2번 원반을 B에서 A로 이동


                1
2       3       4
------------------------
1번 원반을 C에서 A로 이동


1
2       3       4
------------------------
3번 원반을 B에서 C로 이동


1               3
2               4
------------------------
1번 원반을 A에서 B로 이동


                3
2       1       4
------------------------
2번 원반을 A에서 C로 이동

                2
                3
        1       4
------------------------
1번 원반을 B에서 C로 이동
                1
                2
                3
                4
------------------------
원반 4개 하노이탑 운반 횟수 : 15

*/

하노이 타워 문제는 이만하면 해결이 됐을 것으로 생각됩니다. 혹시나 이해가 안 가는 부분이 있다면 얼마든지 댓글 부탁드립니다.