콜라한캔 :: 하노이의 탑

< 하노이의 탑 > 

 재귀를 이용해 푸는 대표적 문제들 중 하나인 하노이의 탑은 이해하기 정말 힘든 문제였다.

하노이의 탑 문제 : https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

위의 그림과 같이 한 곳에 모여져 있는 원판을 아래의 조건을 지키면서 다른 기둥으로 옮기는 문제이다.

1. 한 번에 한 개씩 옮길 수 있다.

2. 자신보다 작은 원판의 위에 올라갈 수 없다.

n 개의 원판을 옮기는데 필요한 최소 경우의 수는 2^n - 1개로, 만약 3개의 원판이라면 7번의 옮기는 행동을 통해 해결할 수 있다.

A    B    C 기둥이 있고, A에서 B로 원판을 이동시키려고 한다고 해보자.

A에서 B로 원판을 이동시킨다는 것은 풀어쓰자면 "A에서 B로 'C를 이용하여' 옮긴다" 는 것이다.

즉, A에서 가장 큰 원판을 제외한 n-1개의 원판을 C로 보내주고 나서야 B에 가장 큰 원판을 옮길 수 있다.

위의 말대로 흘러간다면 A, B, C에는 아래와 같은 상황이 된다.

A : 원판이 존재하지 않음

B : 가장 큰 원판 한 개 있음

C : n - 1 개의 원판이 존재

위와 같다면, 본래 A에서 B로 n개의 원판을 옮겨주는 문제는, C에서 B로 n - 1개의 원판을 옮겨주는 문제로 바뀐다.

즉 점차 문제의 크기가 작아지는 것이다.

#include <stdio.h>
 
void hanoi(char from, char to, char tmp, int n)
{
	static int num = 1; 
	
	// 원판이 한 개인 경우 from에서 to로 이동시켜준다 (가장 큰 원판을 옮기는 것)
	if(n == 1)
	{
		printf("%d : %c 에서 %c 로 원판 %d 이동\n", num++, from, to, n);
	} 
	else
	{
		// from에서 to를 이용하여 n - 1개의 원판을 tmp로 보내준다. 
		hanoi(from, tmp, to, n - 1);
		printf("%d : %c 에서 %c 로 원판 %d 이동\n", num++, from, to, n);
		// tmp에서 from을 이용하여 n - 1개의 원판을 to로 보내준다. 
		hanoi(tmp, to, from, n - 1);
	}  
}

int main()
{
	hanoi('A', 'B', 'T', 3);
	
	return 0;
}