작업순서

1. 동적할당 디버깅 헷갈림

2. 정적 배열로 만들어서 연결 가능?

3. 어디서 어디로 연결하고, 이런 것들을 파악 가능함?

4. 배열의 idx, inputDataNum, output 을 next 로 연결하면 됨

5. 오케이

6. 그리고 DFS 돌려서 연결을 돌리면 됨

 

두 번째 풀이

ingreedy 사용해서 큐를 사용함

1. 배열리스트를 만듬

2. 정적 배열, 링크드 리스트를 만드는 것도 좋음

3. 그럼 관련 링크드 리스트 정해로 풀이하는 사람 것을 찾아야 하는데...

4. 삽입, 삭제가 자유롭고, 정적 배열로 선언해서  푸는 사람.

#include <stdio.h>
#include <malloc.h>

typedef struct Node
{
    int data;
    struct Node* next;
} node;

void make_adj(node*, int);
void dfs(node*, node*, node*, int*, int);
void print(int, node*, node*);
void push(node*, int);
int pop(node*);

int main()
{
    freopen("input.txt", "r", stdin);
    int T;
    int V, E;
    node* arr;
    node* head, *tail;
    int* visited;
    int i;

    setbuf(stdout, NULL);
    for (T = 1; T <= 10; ++T)
    {
        scanf("%d %d", &V, &E);
        arr = (node*)calloc(sizeof(node), V + 1);
        head = (node*)calloc(sizeof(node), 1);
        tail = (node*)calloc(sizeof(node), 1);
        visited = (int*)calloc(sizeof(node), V + 1);
        head->next = tail;
        make_adj(arr, E); // arr+1, arr+2, ... 넣고 들어오는 것의 개수와, 나가는 것을 list 로 연결함
        for (i = 1; i <= V; ++i)
        {
            if ((arr + i)->data == 0)
                dfs(arr, head, tail, visited, i);
        }
        print(T, head, tail);
        free(arr);
        free(head);
        free(tail);
        free(visited);
    }

    return 0;
}

void make_adj(node* arr, int E)
{
    node* newNode;
    node* pos;
    int from, to;
    int i;

    for (i = 0; i < E; ++i)
    {
        scanf("%d %d", &from, &to); // 프로엠서 투로 
        newNode = (node*)calloc(sizeof(node), 1); // 새로운 노드를 만들고
        newNode->data = to; // 새로운 노드는 투를 향함
        newNode->next = NULL; // next는 NULL로 초기화 함
        pos = arr + from; // 프롬으로 가서
        while (pos->next != NULL) // NULL 을 찾은 다음에
            pos = pos->next; 
        pos->next = newNode; // NULL 이라면, 그 자리에 새로운 노드를 연결함 헤드를 기억하고 있는 셈
        (arr + to)->data++;
    }
}

void dfs(node* arr, node* head, node* tail, int* visited, int idx)
{
    node* del;

    visited[idx] = 1;
    while ((arr + idx)->next != NULL)
    {
        del = (arr + idx)->next;
        (arr + idx)->next = del->next;
        del->next = NULL;
        if (visited[del->data] == 1)
            continue;
        else
            dfs(arr, head, tail, visited, del->data);
        free(del);
    }
    push(head, idx);
}

void print(int T, node* head, node* tail)
{
    printf("#%d ", T);
    while (head->next != tail)
        printf("%d ", pop(head));
    printf("\n");
}

void push(node* head, int value)
{
    node* newNode;

    newNode = (node*)calloc(sizeof(node), 1);
    newNode->data = value;
    newNode->next = head->next;
    head->next = newNode;
}

int pop(node* head)
{
    node* del;
    int ret;

    del = head->next;
    ret = del->data;
    head->next = del->next;
    del->next = NULL;
    free(del);

    return ret;
}

#include <stdio.h>

typedef struct {
    int ingreedy;   //노드로 들어오는 화살표의 수.
                    //들어오는 화살표의 수가 없는 노드를 선택해서
                    //계속 진행해야된다.
    int connectList[1001]; //어디노드와 연결되었는지.
    int nodeCnt; //내가가진 자식노드의 수.
    int qFlag; //이노드를 큐에넣었는지 안넣었는지 표시하기위한 플래그
}NODE;

NODE node[1001];

int que[1001];
int front = -1;
int rear = -1;
void enQ(int val) {
    rear++;
    que[rear] = val;
}
int deQ() {
    front++;
    return que[front];
}

void init() {
    for (int i = 0; i<1001; i++) {
        node[i].ingreedy = 0;
        node[i].nodeCnt = 0;
        node[i].qFlag = 0;
    }
    front = -1;
    rear = -1;
}

int main() {
    freopen("input.txt", "r", stdin);
    for (int tc = 1; tc <= 10; tc++) {
        int N, V;//노드의 수, 간선의 수
        int tmpA, tmpB;
        init();
        scanf("%d %d", &N, &V);

        for (int i = 1; i <= V; i++) {
            scanf("%d %d", &tmpA, &tmpB);
            // node[tmpA]의 연결 리스트를 만들고, 오케이, 이렇게 하면 삽입 삭제가 쉽지 않음. 배열이므로
            node[tmpA].connectList[node[tmpA].nodeCnt++] = tmpB; // tmpA 에 연결된 것은 tmpB 이고, nodeCnt++
            node[tmpB].ingreedy++; //tmpB 노드에 다른노드가 들어오므로 ingreedy를 카운팅함.
        }
        printf("#%d ", tc);
        while (rear != N - 1) {
            for (int nI = 1; nI <= N; nI++) {

                if (node[nI].ingreedy == 0 && node[nI].qFlag == 0) {
                    enQ(nI);
                    node[nI].qFlag = 1;
                    //printf("%d ",nI);
                    //현재노드와 연결된 모든 노드들의 ingreedy를 낮춤.

                    for (int i = 0; i<node[nI].nodeCnt; i++) {
                        node[node[nI].connectList[i]].ingreedy--;
                    }
                    node[nI].nodeCnt = 0;//굳이할필요는없지만..
                }
            }
        }
        for (int i = 0; i <= rear; i++) {
            printf("%d ", deQ());
        }

        printf("\n");
    }
    return 0;
}