<5> Q7. 자료구조와 함께 배우는 알고리즘 입문 (C언어)

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int max;
    int prt;
    int *stk;
} IntStack;

char word(int n)
{
    switch (n)
    {
    case 1:
        return 'A';
    case 2:
        return 'B';
    case 3:
        return 'C';
    }
}

int Initialize(IntStack *s, int max)
{
    s->prt = 0;
    if ((s->stk = (int *)calloc(max, sizeof(int))) == NULL)
    {
        s->max = 0;
        return -1;
    }
    s->max = max;
    return 0;
}

int Push(IntStack *s, int x)
{
    if (s->prt >= s->max)
        return -1;
    s->stk[s->prt++] = x;
    return 0;
}

int Pop(IntStack *s, int *x)
{
    if (s->prt <= 0)
        return -1;
    *x = s->stk[--s->prt];
    return 0;
}

int IsEmpty(const IntStack *s)
{
    return s->prt <= 0;
}

void hanoi(int n, int x, int y)
{
    IntStack num, start, via, to;
    Initialize(&num, 100);
    Initialize(&start, 100);
    Initialize(&via, 100);
    int temp;
    while (1)
    {
        while (n > 1)
        {
            Push(&num, n);
            Push(&start, x);
            Push(&via, y);
            n = n - 1;
            y = 6 - x - y;
        }

        printf("원반[%d]를 %c 기둥에서 %c 기둥으로 옮김\n", n, word(x), word(6 - x - y));

        if (IsEmpty(&num))
            break;

        while (1)
        {
            Pop(&num, &n);
            Pop(&start, &x);
            Pop(&via, &y);

            printf("원반[%d]를 %c 기둥에서 %c 기둥으로 옮김\n", n, word(x), word(6 - x - y));
            if (n > 1)
            {
                n = n - 1;
                temp = x;
                x = y;
                y = temp;
                break;
            }
        }
    }
}

int main(void)
{
    hanoi(3, 1, 2);

    return 0;
}

 

처음에 구상했던 데로 코드 작성했더니, 마지막 n = 1에서 무한루프가 일어나서

n = 1일 때는 따로 출력하고 n = 1 일 때 스택이 비어있으면 함수가 종료되도록 만듦