leetcode 210. Course Schedule II

위상 정렬 연습용으로 찾은 문제 210. Course Schedule II.

typedef struct pr {
    int subjectCode;
    struct pr *next;
} COURSELIST;

typedef struct st {
    int NumPrerequisites;
    COURSELIST* after;
} COURSES;

COURSES *courses;
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize){
    int classTaken = 0;
    int *ret = calloc(numCourses, sizeof(int));
    courses = calloc(numCourses, sizeof(COURSES));
    for(int idx=0; idx<prerequisitesSize; idx++){
        int courseIdx = prerequisites[idx][0]; 
        int preIdx = prerequisites[idx][1];

        courses[courseIdx].NumPrerequisites += 1; //선수강과목 갯수 더해주고
        
        COURSELIST *newNext = calloc(1, sizeof(COURSELIST));  // 선수강과목의 '들으면 수강 할 수 있는 강의 리스트'에 추가해줌
        newNext->subjectCode = courseIdx;
        newNext->next = courses[preIdx].after;
        courses[preIdx].after = newNext;
    }
    int *preZeroIdxQueue = calloc(numCourses, sizeof(int));
    int pushPtr = 0;
    int popPtr = 0;
    for(int idx=0; idx < numCourses; idx++) {  // 선수강과목이 없는 과목들을 먼저 큐에 넣음
        if(courses[idx].NumPrerequisites == 0)
        {
            preZeroIdxQueue[pushPtr++] = idx;
        }
    }
    
    while(pushPtr > popPtr) {
        int courseIdx = preZeroIdxQueue[popPtr++];  // courseIdx를 수강했다.
        ret[classTaken++] = courseIdx;  // 큐에서 하나씩 빼서 정답에 담기
        COURSELIST *courList = courses[courseIdx].after;
        while(courList != 0){  // '들으면 수강할 수 있는 과목 리스트'를 돌면서
            int subJectIdx = courList->subjectCode;
            courses[subJectIdx].NumPrerequisites--;  // 선수강 과목 갯수를 -1 해줌 (하나 들었으니까)
            if(courses[subJectIdx].NumPrerequisites == 0) {  //선수강과목이 없어진 과목이 있다면
                preZeroIdxQueue[pushPtr++] = subJectIdx;  // 큐에 넣어준다
            }
            courList = courList->next;
        }
        
    }
    free(courses);
    free(preZeroIdxQueue);
    
    if(classTaken != numCourses) {
        *returnSize = 0;
    } else {
        *returnSize = classTaken;
    }
    
    return ret;
}
/*
0->1
0->2
1->3
2->3

0 : no pre -> 0 should have idx of 1, 2
1 : 0
2 : 0
3 : 1, 2

0
0 : -1
1 : no pre
2 : no pre
3 : 1, 2

1, 2
0: -1
1 : -1
2: -1
3 : 0

3

3
[[1,0],[1,2],[0,1]]
0->1
2->1
1->0
*/

위상 정렬도 queue를 사용해서 풀다보니 보통 자료구조 지원하는 언어 코드가 많았다. 생각해보니 linked list 순회해가며 free 해줬어야 하는데 안해도 통과되었다… 너그러운 리트코드…