하노이의 탑

베트남의 수도 하노이에 있는 불교 사원에 전해지는 이야기 중 다음과 같은 것이 있다고 한다.

다이아몬드로 이루어진 3개의 기둥 중 하나에 64개의 황금 원반이 끼워져 있다. 황금 원반은 크기가 모두 다르며, 아래쪽에서 위쪽으로 갈수록 크기가 작아져서 전체적으로는 원뿔형의 탑을 이루고 있다. 이 64개의 원반을 한 번에 하나씩 움직여 모두 다른 쪽 기둥으로 옮기려고 한다. 단, 옮기는 과정에서 작은 원반 위에 큰 원반이 놓일 수는 없다. 이런식으로 원반들이 처음 있던 기둥에서 다른 기둥으로 모두 옮겨지면 세상이 끝난다는 전설이 있다.

하노이의 탑 문제는 유명하기 때문에 여기까지 검색해서 오신 분들이라면 다른 설명이 필요 없을 것이라고 생각된다.

이 문제는 재귀함수를  이용하여 간단하게 해결할 수 있다. (물론 이해하고 나면 간단하지만, 이해하기 전에는 무지하게 복잡하다.)

편의상 기둥에 번호를 붙여 1번 기둥, 2번 기둥, 3번 기둥이라고 부르자.

1번 기둥에 $n$ 개의 원반이 쌓여 있고, 모두 2번 기둥으로 옮기려고 하면 다음과 같은 과정을 거치면 된다.

i) 1번 기둥에서 가장 밑 원반을 제외한 $n-1$ 개의 원반을 3번 기둥으로 옮긴다.

ii) 1번 기둥에 남은 가장 큰 원반을 2번 기둥으로 옮긴다.

iii) 3번 기둥에 있는 $n-1$ 개의 원반을 2번 기둥으로 옮긴다.

4개의 원반이 있다고 하면 위 과정을 다음과 같이 나타낼 수 있다.

이런 과정을 Go 언어로 표현하면 다음과 같다.

package main

import "fmt"
  
func hanoi(n, a, b int) {
     if n == 1 {
         fmt.Printf("%d -> %d\n", a, b)
     } else {
         c := 6 - a - b
         hanoi(n - 1, a, c)
         hanoi(1, a, b)
         hanoi(n - 1, c, b)
     }
 }

 func main() {
     var num int
     fmt.Println("Number of disks: ")
     fmt.Scanln(&num)
     hanoi(num, 1, 2)
 }

C 언어로 나타내면 다음과 같다.

#include<stdio.h>

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

int main(void) {
	int num;
	printf("Input number of disks : ");
	scanf("%d", &num);
	hanoi(num, 1, 2);
        return 0;
}

a 는 출발지(처음 원반들이 꽂혀 있던 기둥), b 는 도착지(원반들을 옮기고자 하는 기둥), c 는 경유지(원반들이 거쳐가는 기둥) 으로 이해하면 될 것이다. 아마 위 과정과 코드를 같이 보면 충분히 이해가 가리라 생각된다.

결과는 다음과 같다.

Number of disks: 3
1 -> 2
1 -> 3
2 -> 3
1 -> 2
3 -> 1
3 -> 2
1 -> 2

위 출력 결과에서 "1 -> 2" 라는 것은 "1 번 기둥의 맨 위쪽 원반을 2번 기둥으로 옮긴다." 를 나타낸다. 원반이 3개 인 경우는 위와 같이 이동 횟수가 총 7번이 되어야 한다.