하노이 타워

[재귀 알고리즘] 하노이 타워(The Tower of Hanoi) - 재귀, 스택

하노이 타워 문제

하노이 타워 문제는 재귀적으로 해결할 수 있는 대표적인 문제이다.

조건 : 원반은 한번에 한 개씩 옮길 수 있고 큰 원반이 작은 원반 위에 올라가서는 안된다.

원반을 A에서 C로 모두 옮기면 된다.

하노이 타워 패턴

- A에 있는 n개의 원반 중 맨 아래에 있는 n번째 원반을 제외한 나머지 원반을 모두 B로 옮긴다.

- A에 남은 하나의 원반을 C로 옮긴다.

- B의 모든 원반을 C로 옮긴다.

결론을 먼저 말해서 헷갈릴 수도 있지만 하노이 타워를 원반 2개부터 하나씩 증가시키면서 해보면 같은 패턴이 반복 되는 걸 알 수 있다.

하노이 타워의 최소 단위는 2개의 원반이 있을 때인데 작은 원반을 A->B로 옮기고, 큰 원반을 A->C로 옮기고, 작은 원반을 B->C로 옮기면 된다.

원반의 갯수가 늘어났을때도 가장 큰 원반과 나머지 원반으로 두 개로 생각하면 2개의 원반이 있을 때의 반복이 된다.(나머지 원반을 하나의 원반으로 치환한다고 생각하면 좋을 듯 하다.)

Code

#include <stdio.h>
 
int Stack[10];
int cur;
 
//***** Stack 이용을 위한 함수 *****//
void InitStack()
{
    cur = -1;
}
 
void Push(int data)
{
    if (cur >= 10 - 1)
    {
        printf("Stack overflow!!!\n");
        return;
    }
 
    Stack[++cur] = data;
}
 
int Pop()
{
    if (cur < 0)
    {
        printf("Stack is already empty!!!\n");
        return 0;
    }
 
    return Stack[cur--];
}
 
int IsEmpty()
{
    if (cur < 0)
        return 1;
    else
        return 0;
}
///////////////////////////////////////
 
void Print(int n, int from, int to)
{
    printf("원반%d를 %c에서 %c로 이동\n", n, from, to);
}
 
// 하노이 타워 반복문 구현 함수(스택 이용)
void Hanoi(int n, int from, int by, int to)
{
    int bContinue = 1;
    InitStack();
 
    while (bContinue)
    {
        while (n > 1)
        {
            Push(to);
            Push(by);
            Push(from);
            Push(n);
            --n;
            Push(to);
            to = by;
            by = Pop();
        }
        Print(n, from, to);
        if (!IsEmpty())
        {
            n = Pop();
            from = Pop();
            by = Pop();
            to = Pop();
            Print(n, from, to);
            --n;
            Push(from);
            from = by;
            by = Pop();
        }
        else
            bContinue = 0;
    }
}
 
// 하노이 타워 재귀 구현 함수
void HanoiTowerMove(int num, char from, char by, char to){
    if (num == 1){
        printf("원반1을 %c에서 %c로 이동\n", from, to);
    }
    else{
        HanoiTowerMove(num - 1, from, to, by);
        printf("원반%d를 %c에서 %c로 이동\n", num, from, to);
        HanoiTowerMove(num - 1, by, from, to);
    }
}
 
int main(int arc, char** argv){
    printf("하노이 타워 재귀 구현\n");
    HanoiTowerMove(3, 'A', 'B', 'C');
    printf("\n");
    printf("하노이 타워 반복문 구현\n");
    Hanoi(3, 'A', 'B', 'C');
    return 0;
}

정리

코드의 가독성은 재귀를 이용한 함수가 좋지만 성능면에 있어서는 스택을 이용한 함수가 좋다.

스택 사이즈와 원반 갯수를 늘려서 테스트 해보자.