하노이 타워

알고리즘을 하다보면, 자기호출함수 부분을 배울 때, 하노이 타워에 관련되어서는 한번쯤 이야기가 됩니다.  하노이 타워는 대표적인 재귀적 관점이 들어가 있습니다.

 

 

(사진출처 : 위키피디아)

 

하노이 타워가 재귀적 관점이 들어가는 가장 큰 이유는, 작은 디스크 위에 큰 디스크가 올라갈 수 없다는 이유때문입니다.  위 그림에서 첫번째 기둥에 있는 8개의 디스크를 가운데 기둥으로 모두 옮겨야 한다고 하면, 가장 큰 디스크는, 위에 있는 7개의 디스크를 맨 오른쪽 기둥으로 옮기고 나서야 옮길 수 있습니다.  가장 큰 디스크를 가운데 기둥으로 옮긴다음, 맨 오른쪽에 있는 7개의 디스크를 가운데 기둥으로 옮기면 됩니다.

 

그래서 n개의 디스크를 옮긴다면, 다음과 같이 재귀적 알고리즘을 적용할 수 있습니다.

1) n-1개의 디스크를 가장 오른쪽 기둥으로 옮긴다.

2) 제일 큰 디스크를 가운데 기둥으로 옮긴다.

3) n-1개의 디스크를 가장 오른쪽 기둥에서 가운데 기둥으로 옮긴다.

 

이 디스크를 옮기는 횟수는 어떻게 될까요?  n개의 디스크를 옮기는 횟수를 \(T(n)\)이라고 한다면, 재귀적으로 다음과 같이 표현할 수 있습니다.

 

\(T(1)=1\)

\(T(n)=2T(n-1)+1\)

 

위의 점화식은 간단하게 계산할 수 있습니다.

 

\(T(n)=2T(n-1)+1\)

\(T(n)+1=2(T(n-1)+1)\)

\(T(n)+1=2^n\)

\(T(n)=2^n - 1\)

 

그래서 8개의 디스크를 옮기고자 한다면 총 255번의 디스크 옮김이 필요합니다.

 

이것을 프로그램으로 간단하게 작성하면 다음과 같습니다.

 

#include <stdio.h>

void hanoi(int n, int a, int b, int c);
int main()
{
   hanoi(10, 'a', 'b', 'c');
}

void hanoi(int n, int a, int b, int c)
{
  if( n == 0 ) return;
  hanoi(n-1, a, c, b);
  printf("%c->%c\n", a, b);
  hanoi(n-1, c, b, a);
}

 

그런데, 기둥이 3개일 때에는 아주 단순한 알고리즘으로 풀이를 낼 수 있습니다.

기둥이 4개, 5개.. 넘어가게 되면, 이게 단순하지가 않습니다.

휴리스틱한 방법들은 있겠지만, 이 휴리스틱 알고리즘이 최적의 알고리즘이라고 할 수는 없습니다.  (예를 들어서 4개인 경우에는, (n-1)/2 개를 3번째 기둥에 옮기고, (n-1)/2 개를 4번째 기둥으로 옮긴 후에 가장 큰 디스크를 두번째 기둥으로 옮기면 됩니다.  그런데 이것은 최적의 해가 아닙니다.)

 

기둥이 4개일 때, 3개의 디스크라면, a->c, a->d, a->b, d->b, c->b 로.. 5번의 이동이 필요합니다.  

 

기둥이 p개일 때, p보다 작은 디스크를 옮기는 경우에는 확실하게 답을 계산할 수 있습니다.  n-1개의 디스크를 옮겨야할 기둥이 아닌 다른 기둥으로 보내고, 큰 디스크를 옮기고, 다른 기둥에 있는 디스크들을 옮겨오면 되므로, 총 2n-1 번의 이동이면 됩니다.

 

여기에, 기둥이 4개일 때 최적의 해를 적자면요.

 

디스크 갯수	옮긴 횟수
3	5
4	9
5	13
6	17
7	25
8	33
9	41
10	49

 

처음에는 4씩 늘어간다고 생각할 수 있습니다.  그렇지만, 어느순간부터는 그 숫자가 갑자기 늘게 됩니다.  위 결과만 본다면 패턴은 있습니다.  3번마다 증가하는 숫자가 2배씩 늘어나고 있습니다.