열혈 자료구조 - 2-3. 하노이 타워

하노이 타워의 기본 규칙

 

- A개의 세 원반을 C로 옮기기 위해서는 원반 3을 C로 옮겨야 하고 그러기 위해서는 1,2를 B로 옮겨야 함 1,2를 옮기기 위해서는 원반 2를 B로 옮겨야 하고 그러기 위해서는 1을 C로 옮겨야 함

- 이 과정이 4개가 있어도 8개가 있어도 위의 재귀 과정을 반복하게 됨

- 위 과정을 단계로 표현하면

0. 큰 원반 n개를 A에서 C로 이동

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

2. 큰 원반 1개를 A에서 C로 이동

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

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;
}