하노이의 탑 - 시각화

재귀를 이용한 하노이의 탑 시각화(windows와 linux에서만 컴파일 가능)

-sleep 함수 사용에 대해..

windows에서는 windows.h헤더 내에 선언된 Sleep함수(단위 ms)를 이용.

Linux에서는,

linux의 unistd.h에 존재하는 sleep 함수는 최소 대기시간이 1초이다. 만약 1초보다 짧은 시간 동안 프로그램을 재우고 싶다면, 다른 함수가 필요하다.

usleep함수는 microsecond 단위로 대기할 수 있지만, 더이상 잘 사용되지 않는다.

time.h의 nanosleep(시간단위는 nanosecond)을 사용했다(http://stackoverflow.com/a/7684399).

// Visualization: Towers of Hanoi
 
#include <stdio.h>
#include <stdlib.h>
 
#ifdef _WIN32 // Windows (x64 and x86)
#include <windows.h>
#define WAIT(n) Sleep(400*(n))
#define CLRSCR() system("cls")
 
#elif defined __linux__
#include <time.h>
#define WAIT(n) nanosleep((const struct timespec[]){{0, 400000000L * (n)}}, NULL);
#define CLRSCR() system("clear && printf '\e[3J'")
#endif
 
void showTower(int arr[], int n);
void solveHanoi(int *arr, int n, int numDisks, int fromPeg, int toPeg);
void moveDisk(int *arr, int n, int fromPeg, int toPeg);
 
int main(void)
{
    int *arr;
    int size = -1;
    int fromPeg, toPeg;
    
    while (size < 0 || size > 9) {
        printf("원판의 갯수 입력(1-9): ");
        scanf("%d", &size);
    }
    getchar(); // skips '\n'
    for (;;) {
        printf("원판들이 있는 현재 막대기 입력(A, B, C): ");
        fromPeg = getchar();
        if (fromPeg == 'a' || fromPeg == 'A') {
            fromPeg = 0;
            break;
        }
        if (fromPeg == 'b' || fromPeg == 'B') {
            fromPeg = 1;
            break;
        }
        if (fromPeg == 'c' || fromPeg == 'C') {
            fromPeg = 2;
            break;
        }
    }
    getchar(); // skips '\n'
    for (;;) {
        printf("원판들이 이동할 막대기 입력 - 위에서 입력한 것과 다른 막대기(A, B, C): ");
        toPeg = getchar();
        if (fromPeg != 0 && toPeg == 'a' || toPeg == 'A') {
            toPeg = 0;
            break;
        }
        if (fromPeg != 1 && toPeg == 'b' || toPeg == 'B') {
            toPeg = 1;
            break;
        }
        if (fromPeg != 2 && toPeg == 'c' || toPeg == 'C') {
            toPeg = 2;
            break;
        }
    }
    
    /*
    원판 위치에 대한 배열 생성:
    배열의 i번째 멤버의 값은 (i+1)크기의 원판이 위치한 기둥 번호를 나타냄
    0: 기둥 A, 1: 기둥 B, 2: 기둥 C
    ex) arr[] = {0, 2, 1};
    => 크기 1의 원판은 기둥 A, 크기 2의 원판은 기둥 C, 크기 3의 원판은 기둥 B에 있음
    */
    arr = malloc(sizeof(int) * size);
    
    for (int i = 0; i < size; i++) {
        arr[i] = fromPeg;
    }
 
    showTower(arr, size);
    WAIT(1);
    solveHanoi(arr, size, size, fromPeg, toPeg);
    printf("\tdone! :)\n");
    return 0;
}
 
void showTower(int arr[], int n)
{
    int **coord;
    coord = malloc(sizeof(int *) * n);
    CLRSCR();
    if (coord == NULL) {
        printf("malloc failed\n");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < n; i++) {
        if ((coord[i] = malloc(sizeof(int) * 3)) == NULL) {
            printf("malloc failed: %d\n", i);
            exit(EXIT_FAILURE);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++)
            coord[i][j] = 0;
    }
 
    int heightA = 0, heightB = 0, heightC = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        switch (arr[i]) {
        case 0:
            coord[n - 1 - heightA++][0] = i + 1;
            break;
        case 1:
            coord[n - 1 - heightB++][1] = i + 1;
            break;
        case 2:
            coord[n - 1 - heightC++][2] = i + 1;
            break;
        default:
            printf("error: %d\n", i);
            return;
        }
    }
 
    printf("\n\n");
    for (int i = 0; i < n; i++) {
        printf("\t");
        for (int j = 0; j < 3; j++) {
            int num = coord[i][j];
            if (!num)
                printf(":\t");
            else
                printf("%d\t", num);
 
        }
        printf("\n");
    }
    printf("\t_________________\n\tA\tB\tC\n");
 
    //frees the array
    
    for (int i = 0; i < n; i++)
        free(coord[i]);
    free(coord);    
    
    WAIT(1);    
}
 
void solveHanoi(int *arr, int n, int numDisks, int fromPeg, int toPeg)
{
    int sparePeg;
    if (numDisks == 0)
        return;
 
    switch (fromPeg + toPeg) {
    case 0 + 1:
        sparePeg = 2; break;
    case 0 + 2:
        sparePeg = 1; break;
    case 1 + 2:
        sparePeg = 0; break;
    }
    solveHanoi(arr, n, numDisks - 1, fromPeg, sparePeg);
    moveDisk(arr, n, fromPeg, toPeg);
    solveHanoi(arr, n, numDisks - 1, sparePeg, toPeg);
}
 
void moveDisk(int *arr, int n, int fromPeg, int toPeg)
{
    for (int i = 0; i < n; i++) {
        if (arr[i] == fromPeg) {
            arr[i] = toPeg;
            break;
        }
    }
    showTower(arr, n);
}