ProgrammingAlgorithm

하노이탑 알고리즘

하노이탑 알고리즘

하노이탑은 널리 알려져 있는 문제로 3개의 막대가 있고 첫번째 막대에 있는 모든 원판을 3번째 원판으로 최소의 횟수로 이동시키는 문제이다. 이 문제는 알고리즘의 재귀의 대표적 문제로 알려져 있으며 처음 이 방법을 모르면 매우 어려울 수 있으나 개념적 원리를 알고 알고리즘을 구현하면 생각보다 의외로 간단하고 깔끔한 코드가 나오는 문제이다.

원리는 간단한데 마지막 n번째의 원판을 옮기기 위해서는 먼저 n-1개의 원판을 다른곳으로 옮겨놔야 3번으로 옮길 수 있다. 따라서 다음과 같은 순서가 재귀적으로 발생한다.

  1. 1번 기둥에 있는 n번째 원판을 3번 기둥으로 옮기기 위해 n-1개의 원판을 2번 기둥으로 모두 옮긴다.
  2. n번째 원판을 1->3으로 옮긴다.
  3. 2번 기둥에 있는 n-1개의 원판을 비어있는 1번 기둥을 이용하여 3번 기둥으로 모두 옮긴다.

재귀를 이해하기 쉽게 1번에서의 재귀로 들어갔다고 해보자.

각각 hanoi(n,from,by,to)를 n개의 원판을 by를 이용해 to로 옮긴다라고 생각하면 되는데 n번째의 원판을 3으로 옮기기 위해서는 n-1번째의 원판이 2로 이동되어 있어야 한다. 또 n-1번째의 원판이 2로 이동되기 위해서는 n-2개의 원판이 3으로 이동되어 있어야 한다. 이 과정을 반복하는데 n이 1일경우 그냥 자유롭게 옮길 수 있으므로 from ->to 로 옮기면 된다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<set>
#include<algorithm>

using namespace std;

void hanoi(int n, int from, int by, int to)
{
	if (n == 1)
	{
		printf("이동 %d -> %d\n", from, to);
		return;
	}

	hanoi(n - 1, from, to, by); // n-1 개의 원판을 1에서 3을 이용하여 2로 옮긴다.
	printf("이동 %d -> %d\n", from, to);
	hanoi(n - 1, by, from, to); // n-1개의 원판을 2에서 1을 이용하여 3으로 옮긴다.
}

void main()
{
	hanoi(5, 1, 2, 3);

}
공유하기