[알고리즘] Towers of Hanoi - 하노이의 탑 알고리즘

분할정복 알고리즘을 사용하여 하노이탑(Towers of Hanoi) 문제를 풀어보자.

 

 

하노이탑은 말뚝 3개와 크기가 모두 다른 구멍난 디스크 n개로 구성되어 있다.

 

문제는 한 말뚝에 쌓여있는 n개의 디스크를 모두 지정한 말뚝으로 옮기는 것이다.

---

규칙

문제를 풀 때 다음 규칙을 반드시 준수해야 한다.

(1) 세 개의 말뚝 이외에는 디스크를 놓을 수 없다.
(2) 한 번에 하나의 디스크만 옮길 수 있고, 말뚝의 맨 위에 있는 디스크만 옮길 수 있다.
(3) 큰 디스크를 작은 디스크 위에 올려놓을 수 없다.

디스크의 수가 n개인 하노이 탑은 최소 $2^n - 1$단계로 풀 수 있다.
위 사진은 디스크의 수가 3개인 하노이 탑이 $2^3 - 1 = 7$단계를 거쳐 풀이됨을 보여준다.

---

알고리즘

일단, 세개의 기둥에 각각 source, destination, auxiliary 라고 이름을 붙이자.

 

디스크의 수가 1개라면, source에서 auxiliary를 거치지 않고 바로 destination으로 디스크를 옮겨 끝낼 수 있다.

 

디스크의 수가 2개라면...

1. 가장 작은 크기의 (맨위에있는) 디스크를 auxiliary 기둥으로 옮긴다.
2. 그다음으로 큰 (바닥에 있는) 디스크를 destination 기둥으로 옮긴다.
3. 마지막으로, auxiliary 기둥에 있는 가장 작은 크기의(맨위에있던) 디스크를 destination 기둥으로 옮긴다. 

이제 n개의 디스크에 대한 알고리즘으로 표현해보자.

 

알고리즘은 크게 두 파트로 나눌 수 있을것이다. 가장 큰 디스크 (바닥에 있는 n번째 디스크)와 다른 디스크(n-1) 이렇게 말이다.

최종적으로 가장 큰 디스크(바닥에 있는 n번째 디스크)를 destination 기둥으로 옮긴 후, 다른 디스크(n-1)를 위에 올려야하는데 재귀를 사용하여 생각해볼 수 있을것같다.

Step 1. : 맨위에서부터 n-1번째까지 디스크를 source에서 auxiliary로 옮긴다.
Step 2. : n번째 디스크를 source에서 destination으로 옮긴다.
Step 3. : n-1번째 디스크를 auxiliary에서 destination으로 옮긴다.

위의 알고리즘을 의사코드로 나타내면

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

이렇게 나타낼 수 있을것이다.

 

이 페이지에서 위 알고리즘을 시뮬레이션을 해볼 수 있는데, 아래 사진의 디스크가 4개인 경우를 예로 시뮬레이션 해보자.

A = source / B = auxiliary / C = destination

4개의 디스크를 C로 옮기기 위해서는 먼저 1, 2, 3 (n-1) 디스크를 B로 옮기고, 4번 디스크를 C로 옮겨야 한다.

이렇게... 맨 아래 디스크와 그 위의것들(?) 두 파트로 나눠 옮긴다고 생각하자.

그 다음엔 B에 있는 3개의 디스크를 C로 옮겨야하는데...

3개의 디스크를 C로 옮기기 위해서는 먼저 1, 2 (n-1) 디스크를 A로 옮기고, 3번 디스크를 C로 옮겨야 한다.

이렇게!

그 다음엔 A에 있는 2개의 디스크를 C로 옮겨야하는데...

2개의 디스크를 C로 옮기기 위해서는 먼저 1 (n-1) 디스크를 B로 옮기고, 2번 디스크를 C로 옮겨야 한다.

시간은 신경쓰지 말자;;

$2^n - 1$ 즉 $2^4 - 1=15$의 횟수로 성공함을 볼 수 있다.

위에서 이야기했지만, 크게 두 파트로 나눠 맨 아래 판을 순차적으로 옮긴다고 생각하면 쉽게 이해할 수 있을것이다.

---

증명

디스크의 수가 n개인 하노이 탑은 최소 $2^n - 1$단계로 풀 수 있다.

따라서 점화식을 사용하여 $S(n)=2^n-1$을 증명해보자.(n이 디스크의 개수라면, $S(n)$은 옮기는 횟수이다.)

 

n개의 원판을 옮길 때 거치는 과정을 총 3단계로 나눌 수 있다고 위에서 언급하였다.

Step 1. : n-1개의 디스크를 source에서 auxiliary로 옮긴다.
Step 2. : n번째 디스크 (가장 큰 디스크)를 source에서 destination으로 옮긴다.
Step 3. : n-1개의 디스크를 auxiliary에서 destination으로 옮긴다.

Step 1 을 거치는데 걸리는 최소 이동횟수는, n-1개의 원판을 다른곳에 옮기는 것이므로 $S(n-1)$이다.

Step 2 는 1개의 원판만 옮기면 되기 때문에 1이다.

Step 3 은 n-1개의 원판을 이동시키는 것이므로 $S(n-1)$이다. 

 

위 과정을 모두 더하면 $S(n)$이 되는데, 이를 점화식으로 만들어보면, $S(n)=S(n-1)+1+S(n-1)=2S(n-1)+1$ 이라는 점화식이 만들어진다.

 

양변에 1씩 더하고 우변을 2로 묶으면 식은 $S(n)+1=2{S(n-1)+1}$ 이 된다. 그 다음, n에 n, n-1, ... 3, 2 을 대입한 후 양 변을 각각 곱해준다.

 

$S(n)+1=2{S(n-1)+1}$

$S(n-1)+1=2{S(n-2)+1}$

$S(n-2)+1=2{S(n-3)+1}$

...

$S(2)+1=2{S(1)+1}$

양 변을 각각 곱하면

$(S(n)+1)(S(n-1)+1)...(S(2)+1)=2^{(n-1)}(S(n-1)+1)(S(n-2)+1)...(S(1)+1)$

양변을 $(S(n)+1)(S(n-2)+1)...(S(2)+1)$로 나누면

$(S(n)+1)=2^{(n-1)}(S(1)+1)$

$S(1)=1$이므로

$S(n)+1=2^{(n-1)}(1+1)=2^n$

따라서 $S(n)=2^n-1$

 

양 변을 각각 곱하고 나서 $2^{(n-1)}$이 나온 이유는, 곱한 식이 총 n-1개이며 각 식마다 2가 1개씩 있어서이다.

또, $S(1)=1$인 이유는, 1개의 디스크를 다른 기둥으로 옮기는 데 필요한 최소 횟수가 1번이기 때문이다.

 

따라서 위의 최종 식, $S(n)=2^n-1$ 이 나오게 되는 것이다.