[알고리즘] 하노이의 탑

2009. 05. 06 (水)

883년 프랑스 수학자 루카스(Lucas. E.)는 하노이 탑이라고 불려지게 된 유명한 문제를 고안해냈습니다. 전설에 따르면 천지 창조 시에 가장 가운데 작은 구멍이 뚫린 64개의 금으로 된 원판이 하노이의 한 사원에 보관되어 있었다고 합니다. 이들 원판은 어느 것도 크기가 같지 않으며 그림과 같이 작은 원판이 큰 원판 위에 오도록 포개어져, 세 개의 기둥가운데 한 개에 끼워져 있었다고 합니다. 이러한 모양이 탑과 비슷하다 하여 하노이탑(Hanoi Tower) 이라고 부릅니다

1.     하노이 탑 정의

-       원판을 세 번째로 모두 옮겨놓아야 한다. 이때도 작은 원판이 큰 원판 위에 있어야 한다.

-       원판을 옮길 때는 반드시 한 번에 한 개씩 옮길 수 있고 두 번째 막대기를 이용할 수 있습니다.

-       옮기는 과정에서 절대로 큰 원판이 작은 원판 위에 놓이지 않아야 합니다.

-       최대공약수를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다.

 

2.     하노이 탑의 규칙 찾기

-       원판이 1개일 때

1.      A에서 원판 1을 C로 이동

 

-       원판이 2개일 때

1.     A에서 원판1을 B로 이동

2.     A에서 원판2을 C로 이동

3.     B에서 원판1을 C로 이동

 

-       원판이 3개일 때

1.     A에서 원판1을 C로 이동

2.     A에서 원판2을 B로 이동

3.     C에서 원판1을 B로 이동

4.     A에서 원판3을 C로 이동

5.     B에서 원판1을 A로 이동

6.     B에서 원판2을 C로 이동

7.     A에서 원판1을 C로 이동

 

3.     하노이 탑 알고리즘

 

-       순서대로 1부터 n까지 원판이 있고 A, B, C 3개의 막대기가 있는 경우 하노이 탑 문제를 해결하는 방법은 다음과 같다.

 

1.     A 막대기에서 2번부터 n번째까지 n-1개의 원판을 B막대기로 이동한다.

2.     A 막대기에서 1번 원판을 C막대기로 이동시킨다.

3.     B 막대기에서 2번부터 n번째 까지 n-1개의 원판을 C로 이동시킨다.

4.   소스

 

#include "stdafx.h"

#include <stdio.h>

void Hanoi(int n, char from, char middle, char to);

int _tmain(int argc, _TCHAR* argv[])

{

        int coin;

        printf("원판의개수를입력하시요:");

        scanf("%d", &coin);

        printf("\n");

        Hanoi(coin, 'A', 'B', 'C');

        return 0;

}

 

void Hanoi(int n, char from, char middle, char to)

{

        if(1==n)

        {

               printf("%c - %02d -> %c\n", from, n, to);

        } 

        else

        {

               Hanoi(n-1, from, to, middle);

               printf("%c - %02d -> %c\n", from, n, to); 

               Hanoi(n-1, middle, from, to);

        }

}