[알고리즘] 재귀(Recursion) - 하노이탑

하노이의 탑은 3개의 기둥과 서로 크기가 다른 여러개의 원판들이 있을 때 이 원판들을 한 기둥으로부터 다른 기둥으로 옮기는 일종의 게임입니다.

게임을 시작하기 전 초기 상태는 3개의 기둥 중 하나의 기둥에 모든 원판들이 아래에서부터 크기가 큰 순으로 놓여져 있으며, 최종 목표는 이 원판들을 하나씩 옮겨서 순서 그대로 다른 기둥에 쌓는 것입니다. 이 때 2가지 규칙이 있습니다.

1. 원판은 한 번에 한 개씩만, 기둥에서 기둥으로만 움직일 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

 

하노이탑은 재귀함수를 사용하여 해결할 수 있는 대표적인 문제입니다. 1, 2, 3번 기둥이 있고, n 개의 서로 다른 크기의 원판들이 있다고 할 때 1번 기둥에 쌓여져 있는 n 개의 원판들을 모두 3번 기둥으로 최소의 이동횟수로 옮기는 순서를 출력하는 프로그램을 작성해보도록 합시다.

 

3번 기둥에 순서대로 원판들을 쌓기 위해서는 가장 큰 원판을 1번 기둥의 맨 아래에서 3번 기둥의 맨 아래로 이동시켜야 합니다. 그러기 위해서는 가장 큰 기둥 위에 쌓여져 있는 n-1 개의 원판들을 임시로 2번으로 옮긴 후 가장 큰 원판을 3번으로 옮기고 나서, 2번에 쌓아둔 n-1 개의 원판들을 다시 3번의 가장 큰 원판 위에 차례대로 쌓으면 됩니다. 이 과정을 재귀를 사용하여 표현하면,

Hanoi(int n, int from, int to){
    Hanoi(n-1, from, 6-from-to);
    printf("%d -> %d", from, to);
    Hanoi(n-1, 6-from-to, to);
}

 

이렇게 재귀 함수를 구성하고, 함수가 멈추는 base case 를 설정하여 주면,

Hanoi(int n, int from, int to){
    if(n == 0) return ;
    Hanoi(n-1, from, 6-from-to);
    printf("%d -> %d", from, to);
    Hanoi(n-1, 6-from-to, to);
}

 

이런 식으로 하노이탑 문제를 해결할 수 있습니다.

더불어, 하노이탑을 해결하는 원판의 최소 이동횟수도 재귀함수를 사용하여 구할 수 있는데, 위 함수를 조금 변형하여서 해결할 수 있습니다.

int Hanoi(int n, int from, int to){
    mid = 6 - from - to;
    if(n == 1) return 1;
    else return Hanoi(n-1, from, mid) + 1 + Hanoi(n-1, mid, from);
}

 

 

이렇게 함수를 만들고 실행하여 보면, 하노이탑의 최소 이동횟수가 1, 3, 7, 15 ... 이렇게 익숙한 수가 나오는 것을 볼 수 있습니다.
하노이탑의 최소 이동횟수를 나타내는 함수를 f(n) 이라고 하면,

 

$f(n) = 2f(n-1) + 1$
$f(n) + 1 = 2(f(n-1) + 1)$

 

이렇게 표현이 가능하고, f(n) + 1 을 g(n) 이라고 두고 생각하면,

 

$g(n) = 2g(n-1)$

 

이렇게 등비수열로 표현이 되고, 이를 일반항으로 표현하면

 

$g(n) = 2^n$
$f(n) = 2^n - 1$

 

이 된다는 것을 알 수 있습니다.