알고리즘 :: 컴파일러도 “귀찮다” 라고 말하는 하노이 탑 문제

19세기경 유럽에서는 “창세기부터 지금까지 브라마 사원에서 계속되고 있다”는 선전용 문구와 함께 유명했던 “하노이 탑”이라는 게임이 있었답니다.

전설에 의하면 아직도 계속되고 있다는 이 게임은 창세기에 그 사원의 사제가 하나님으로부터 다이아몬드로 된 세 개의 말뚝에 꽂혀 있는 구리 제단을 받았는데, 첫 번째 말뚝에는 금으로 된 64개의 원반이 쌓여 있었고, 각 원반은 바로 밑에 있는 원반보다 조금씩 작았습니다. 사제는 모든 원반을 두 번째 말뚝을 이용하여 세 번째 말뚝에 옮기는 임무를 부여 받았는데, 아래와 같은 규칙이 있었습니다.

1. 원반은 한번에 하나씩만 옮겨야 한다.
2. 위에 놓인 원반은 아래의 원반보다 클 수 없다.

만일 그 사제가 64개의 원반을 옮기는 작업을 다 끝내면, 이 세상에는 종말이 온다고 합니다.

#include <stdio.h>

int cnt = 0;

void moveHanoi(char, char, char, int);

int main(void)
{
    int n;

    printf("하노이 탑에서 옮기려는 원반의 수는? >> ");
    scanf("%d", &n);

    moveHanoi('A', 'B', 'C', n);
    return 0;
}

void moveHanoi(char from, char via, char dest, int n)
{
    if(n == 1) {
        printf("\n%5d: 말뚝 %c 에서 말뚝 %c 로 원반 %d 을 이동 \n", ++cnt, from, dest, 1);
    }
    else {
        moveHanoi(from, dest, via, n-1);
        printf("%5d: 말뚝 %c 에서 말뚝 %c 로 원반 %d 을 이동 \n", ++cnt, from, dest, n);
        moveHanoi(via, from, dest, n-1);
    }
}