2-3 재귀의 활용 - 하노이 타워

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

하노이 타워는 '하나의 막대의 원반을 다른 하나의 원반에 그대로 옮기는 방법'을 다룬다.

하노이 타워는 다음의 조건을 만족하면서 옮겨야한다.

• 위에서부터 한 번에 하나씩만 
• 작은 원반 위에 큰 원반 올 수 없음

원반을 C 막대로 옮겨야하기에 B 막대의 도움이 필요하다

 

이 하노이 타워에는 패턴이 있는데

원반이 몇개가 되었든 맨 밑의 원반을 제외한 나머지들을 B에,  맨 밑에 있는 원반을 C에 옮긴 다음, 그런 다음 B에 있던 원반들을 다시 C에 옮겨야한다.

 

이 패턴을 재귀적으로 구현을 하면 다음과 같다.

참고 : 위에서부터 옮기므로 n - 1은 맨 밑을 제외한 수다

 

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) // 이동할 원반의 수가 1개라면
	{
		printf("원반1을 %c에서 %c로 이동 \n", from, to);
	}
	else
	{
		HanoiTowerMove(num - 1, from, to, by);					   // 3단계 중 1단계
		printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); // 3단계 중 2단계
		HanoiTowerMove(num - 1, by, from, to);					   // 3단계 중 3단계
	}
}

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

 

HanoiTowerMove(int num, char from, char by, char to)

 

인자로 num은 원반의 갯수, from에서 by를 거쳐 to로 이동하는 의미로 해석하면된다.

from, by, to가 매번 바뀌어서 재귀함수의 인자로 전달 되는 이유는 위에 했던 A B C 패턴에 그대로 from by to를 넣은것이기 때문이다.