[자료구조] 재귀 - 하노이 타워 (The Tower of Hanoi)

하노이 타워는 재귀함수의 힘을 보이는 대표적인 예로 꼽힌다. 

 

하노이 타워 문제는 '하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법'에 관한 것이다.

 

 

다음 제약 조건을 만족하면서 A의 원반을 C로 옮겨야 한다.

 

1. 원반은 한 번에 하나씩만 옮길 수 있다.
2. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.

 

 

이를 해결하기 위한 과정은 3가지가 있다.

 

1. 작은 원반 n-1개를 A에서 B로 이동 
2. 큰 원반 1개를 A에서 C로 이동
3. 작은 원반 n-1개를 B에서 C로 이동

+ 여기에 탈출조건이 더해져야 한다.

 

=> 이를 재귀적으로 활용하면 하노이타워 문제를 해결할 수 있다.

 

 

 

 

<코드>

#include <stdio.h>

void HanoiTowerMove(int num, char from, char by, char to)
{
	if (num == 1)
	{
		printf("원반1을 %c에서 %c로 이동 \n", from, to);
	}
	else
	{
		HanoiTowerMove(num - 1, from, to, by); 
		printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); 
		HanoiTowerMove(num - 1, by, from, to); 
	}
}


int main()
{
	// 막대A의 원반 3개를 막대B를 경유하여 막대C로 옮기기
	HanoiTowerMove(3, 'A', 'B', 'C');
	return 0;
}

 

 

<실행결과>