[백준] 2623번 음악프로그램 (= music program) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/2623

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

#define DEBUG 0
#define MAX_QUEUE_SIZE 1001

typedef struct _queue {
int mem[MAX_QUEUE_SIZE];
int front;
int back;
} queue;
queue *qu;

int N, M;
bool graph[MAX_QUEUE_SIZE][MAX_QUEUE_SIZE];    //가수 순서 규칙 저장
int arrResult[MAX_QUEUE_SIZE];    //최종 가수 순서 저장
int resultIdx;

void check(int);    //인자로 들어온 가수 이전에 해야하는 가수 없는지 검사
bool topologicalSorting(void);    //최종 가수 정렬하면서 정렬 가능 여부 반환

void initQueue(queue *);
bool empty(queue *);
void pop(queue *);
void push(queue *, int);
size_t size(queue *);
int front(queue *);
int back(queue *);

/*========================================*/
int main(void)
{
    int inCount;

    qu = (queue *)malloc(sizeof(queue));
    scanf("%d %d", &N, &M);

    //필요한 값들 초기화
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            graph[i][j] = false;
            arrResult[j] = 0;
        }
    }
    resultIdx = 1;

    //입력 받아서 graph에 저장
    for (int i = 0; i < M; i++) {
        int before, after;

        scanf("%d", &inCount);
        scanf("%d", &before);

        for (int j = 0; j < inCount - 1; j++) {
            scanf("%d", &after);
            graph[before][after] = true;
            before = after;
        }
    }

    //i 이전에 해야하는 가수가 없는지 검사
    for (int i = 1; i <= N; i++)
        check(i);

    //모든 가수가 정렬 완료되면 결과 출력
    if (topologicalSorting()) {
        for (int i = 1; i <= N; i++)
            printf("%d\n", arrResult[i]);
    }
    //정렬이 불가능해지면 0 출력
    else {
        printf("0\n");
    }

    free(qu);
    return 0;
}
/*========================================*/

void check(int pos)
{
    bool before = false;

    for (int i = 1; i <= N; i++) {
        //pos 이전에 해야하는 가수가 있는지 검사
        if (graph[i][pos]) {
            before = true;
            break;
        }
    }
    //pos 이전에 해야하는 가수가 없으면 queue에 push (제거 가능)
    if (!before) {
        push(qu, pos);
    }
    return;
}

bool topologicalSorting(void)
{
    while (!empty(qu)) {
        int cur = front(qu);
        pop(qu);

        //queue의 front에 들어 있는 가수의 모든 연결 제거
        for (int i = 1; i <= N; i++) {
            if (graph[cur][i]) {
                graph[cur][i] = false;
                check(i);
            }
        }
        //결과에 최종적으로 순서 결정
        arrResult[resultIdx++] = cur;
    }
    if (arrResult[N])
        return true;
    else
        return false;
}

void initQueue(queue *qu)
{
    for (int i = 0; i < MAX_QUEUE_SIZE; i++)
        qu->mem[i] = 0;
    qu->front = -1;
    qu->back = -1;
    return;
}
bool empty(queue *qu)
{
    if (qu->front == qu->back) { return true; }
    else { return false; }
}
void pop(queue *qu)
{
    if (!empty(qu))
        qu->mem[++qu->front] = 0;
    return;
}
void push(queue *qu, int data)
{
    qu->mem[++qu->back] = data;
    return;
}
size_t size(queue *qu) { return (size_t)(qu->back - qu->front); }
int front(queue *qu) { return qu->mem[qu->front + 1]; }
int back(queue *qu) { return qu->mem[qu->back]; }