[디딤돌 자료구조와 알고리즘 with C] 3.2 하노이 타워

3. 2 하노이 타워

하노이 타워.c

 재귀 알고리즘 중에 하노이 타워가 있습니다.

 

 하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다.

[그림 3.1] 하노이 타워

 

 이 문제를 재귀적으로 해결하면 다음과 같은 방법으로 해결할 수 있습니다.

 

가정: n-1개의 돌을 옮길 수 있다.

가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다.

규칙에 의해 1개의 돌을 A에서 C로 옮깁니다.

가정에 의해 B에 있는 n-1개의 돌을 A를 이용하여 C로 옮깁니다.

따라서 n개의 돌을 옮길 수 있다.

 

이를 의사코드(pseudo code)로 나타내면 다음처럼 표현할 수 있습니다. 탈출 조건을 표현하고 있음을 확인하세요.

Hanoi(src, use, dest, n)

    조건 n<=0

        종료

    Hanoi(src,dest,use,n-1)

    Move(src,dest)

    Hanoi(use,src,dest,n-1)

 

 알고리즘을 보면 재귀 호출 전보다 n은 1 감소하고 n이 1이 되면 재귀를 탈출하므로 탈출 조건에 근접함을 알 수 있습니다.

 

 

 

3.2.1 하노이 타워 알고리즘 성능 분석

 하노이 타워 알고리즘 성능을 분석합시다.

 

 n 개 돌을 옮기는 데 걸리는 수행 시간을 T(n)이라고 합시다.

 

 하노이 타워 알고리즘의 수행 시간 T(n)은 T(n-1) 2번과 Move 1번으로 진행합니다.

T(n) = 2*T(n-1) + 1 = 2 *T(n-2) + 2 +1 = 2^2*T(n-3) +4+2+1 = ... = 2^n -1

 

 따라서 하노이 타워 알고리즘 수행 시간은 O(2^n)이라고 말할 수 있습니다.

[그림 3.2] 하노이 타워 알고리즘

 

 

3.2.2 하노이 타워 알고리즘 구현

 하노이 타워 알고리즘을 구현합시다. 알고리즘은 입력 인자로 세 개의 기둥과 돌의 개수를 받아야 합니다.

void Hanoi(const char *src, const char *use, const char *dest, int n)

{

 만약 돌이 없으면 아무 것도 수행하지 않고 함수를 종료합니다. 즉 탈출 조건입니다.

    if(n<=0)

    {

        return;

    }

 먼저 src에 있는 n-1개의 돌을 dest를 이용하여 use로 옮깁니다. 이 때 재귀로 호출합니다.

    Hanoi(src,dest,use,n-1);

 그리고 src에 있는 돌을 dest로 옮깁니다.

    printf("move %s -> %s\n",src,dest);

 마지막으로 use에 있는 n-1개의 돌을 src를 이용하여 dest로 옮깁니다.

    Hanoi(use,src,dest,n-1);

}

 다음처럼 간단하게 테스트 코드를 작성하여 확인해 보세요.

int main()

{

    Hanoi("a","b","c",3);

    return 0;

}

 

 다음은 하노이 타워 알고리즘을 실행했을 때 화면입니다.

[그림 3.3] 하노이 타워 실행 화면

 

 

 

 수행 속도를 확인하기 위해 다음과 같이 테스트 코드를 수정해서 확인해 보면 단지 2개의 돌을 늘렸는데 수행 시간은 앾 4배 증가하는 것을 볼 수 있습니다.

int main()

{

    clock_t st,et;

    st = clock();

    Hanoi("a","b","c",5);

    et = clock();

    printf("%d개의 돌 옮기기:%d\n",5,et-st);

 

    st = clock();

    Hanoi("a","b","c",7);

    et = clock();

    printf("%d개의 돌 옮기기:%d\n",7,et-st);

    return 0;

}

[그림 3.4] 하노이 타워 수행 속도 비교 화면