하노이 탑

아래의 그림에서 A 타워에 놓인 N개의 원반을 규칙을 만족하며 모두 C로 이동시켜야 한다.

 규칙 1. 최소한의 횟수만 움직여야 한다.

 규칙 2. 더 큰 원반이 자신보다 작은 원반위로 올 수 없다.

 규칙 3. 동시에 하나의 원반만 다른 기둥으로 옮길 수 있다.

---

위의 하노이 탑 문제는 보통 재귀로 풀게된다. 재귀로 풀기위해서는 보통 몇 번의 경우를 생각해보고 일정한 규칙을 반복하면 그것을 통해서 재귀적으로 함수를 호출하면 된다.

사실 나도 이 문제가 처음에 잘 이해가 되지않았지만 손으로 해보니깐 알게되었다.

헷갈린다면 원판이 3개가 있다고 가정하고 그림을 그려가면서 생각해보면 도움이 될 것이다.

출처: https://shoark7.github.io/programming/algorithm/tower-of-hanoi

---

정답 소스는 아래와 같다.

#include<stdio.h>

void hanoi(int n, char start, char work, char target);

int main() {
	int n;
	printf("Number of disk. > ");
	scanf_s("%d", &n);

	//n개의 원반을 'A' 기둥에서 'C' 기둥으로 모두 옮긴다.
	hanoi(n, 'A', 'B', 'C');

	getchar();
	return 0;
}

void hanoi(int n, char start, char work, char target) {

	if (n == 1)	//옮겨야 할 원반이 하나 뿐일 때
	{
		printf("%d번 원반을 %c에서 %c로 이동\n", n, start, target);
	}
	else   //옮겨야 할 원반이 두 개 이상일 때
	{
		hanoi(n - 1,start,target,work);
		printf("%d번 원반을 %c에서 %c로 이동\n", n, start, target);
		hanoi(n - 1, work, start, target);
	}
}

 

원반 3개일 때 결과

원반 4개일 때 결과