[C언어 알고리즘] 3.2.2 하노이 타워 알고리즘 구현

[C언어 알고리즘] 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] 하노이 타워 수행 속도 비교 화면