[카테고리:] <span>자료구조와 알고리즘</span>

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

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;
}

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

수행 속도를 확인하기 위해 다음과 같이 테스트 코드를 수정해서 확인해 보면 단지 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;
}