하노이의 탑

 

하노이의 탑

 알고리즘 예제에서 단골 문제이다. 그만큼 머리를 많이써야하는 알고리즘 중 하나이다.

하노이의 탑 문제를 해결하는 프로그램을 작성할 때 알고리즘을 짜기 위해 머리를 쥐어짤 필요는 없다.

검색창에 하노이의 탑이라고 검색하면 기본적인 규칙과 풀이순서가 제공된다.

 

문제

다음 규칙을 지키며 막대A에 쌓여있는 원판 b개를 막대C로 옮기는 것이다.

1. 한 번에 하나의 원판만 이동할 수 있다.

2. 맨 위에 있는 원판만 이동할 수 있다.

3. 크기가 작은 원판 위 에 큰 원판이 쌓일 수 없다.

4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야한다. 

 

다음 사진은 이해를 돕기위한 원판이 3개일 때의 풀이 과정이다.

 

위 사진을 분석하여 알고리즘을 도출할 수있다.

막대A에서 C로 모두 옮기기 위해 B를 임시 버퍼로 사용한다.

n-1개의 원판을 A에서 B로 임시로 옮긴다.

n번쨰 원판(재일 큰 원판)을 A에서 C로 옮긴다.

n-1개의 원판을 B에서 C로 옮긴다.

 

그럼 어떻게 n-1개의 원판을 옮기느냐?

재귀호출을 통해 해결한다.

현재 작성중인 함수의 파라미터를 n-1로 바꾸어 순환호출하면 된다.

 

소스

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to) {
   if( n==1 ) printf("원판 1을 %c 에서 %c으로 옮긴다.\n",from,to);
   else {
      hanoi_tower(n-1, from, to, tmp);
      printf("원판 %d을 %c에서 %c으로 옮긴다.\n",n, from, to);
      hanoi_tower(n-1, tmp, from, to);
   }
}
 
main() {
hanoi_tower(4, 'A', 'B', 'C');
}

원판의 이동 과정을 printf문으로 출력하는 소스이다.

필요에 따라 파라미터를 그래픽으로 활용하던

횟수를 카운트하여 몇번 움직여야하는지를 계산하던

본인 능력껏 활용하라.