[c언어] 하노이탑 문제 (문제 설명, 예제)

하노이의 탑

그림판으로 그린 하노이탑 ~

하노이의 탑은 고대 인도로부터 시작한 일종의 퍼즐입니다.

목표는 아래의 조건을 지키며 한 축에 있는 원반들을 모두 다른 축으로 옮기는 것입니다. 

조건

• 한번의 하나의 원판을 이동할 수 있다. 
• 맨 위에 있는 원판만 이동이 가능하다. 
• 크기가 작은 원판위에 크기가 큰 원판이 올라갈 수 없다. 

두 개의 축만 있다면 퍼즐이 불가능하기 때문에  임시의 축을 사용합니다. 

 

예제

다음 예제는 원반의 개수를 입력받고 하노이의 탑을 푸는 예제이다. 

A축에 원판이 있고 B축을 이용하여 최종적으로 C축으로 모두 옮기는 과정을 나타내는 예이다. 

원판의 크기는 숫자를 통해 나타내었다. 

#include <stdio.h>

void hanoi(int n, char from, char tmp, char to);


int main(void) {
	int n = 0;
	printf("원반의 개수를 입력하시오: ");
	scanf("%d", &n);
	
	hanoi(n, 'A', 'B', 'C');
	return 0;
}

void hanoi(int n, char from, char temp, char to) {
	if (n == 1) {
		printf(" 1번 원판을 %c축에서 %c축으로 옮긴다. \n", from, to);
	}
	else {
		hanoi(n - 1, from, to, temp);
		printf(" %d번 원판을 %c축에서 %c축으로 옮긴다. \n", n, from, to);
		hanoi(n - 1, temp, from, to);
	}
}

다음은 원판의 개수를 4로 입력하여 받은 결과이다. 

 

 

이미지 정리