LeetCode (C/C++) 207. Course Schedule

https://leetcode.com/problems/course-schedule/

---

풀이

위상정렬을 사용한 문제.

---

코드

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector <int> seq[2000];
        int inDegree[2000] = {0, };
        queue <int> q;

        // 노드의 레벨과 before-now 정보 저장
        for (int i = 0; i < prerequisites.size(); i++) {
            int now = prerequisites[i][0], before = prerequisites[i][1];
            seq[now].push_back(before);
            inDegree[before]++;
        }

        // 레벨이 0이면 큐에 삽입
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0)
                q.push(i);
        }

        // 모든 노드 탐색
        while (q.size()) {
            int now = q.front();
            q.pop();
            for (int next:seq[now]) {
                inDegree[next]--;
                if (inDegree[next] == 0)
                    q.push(next);
            }
        }

        // 탐색 후 노드의 레벨이 1 이상 = 모든 노드를 탐색하지 못함 -> return false
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i])
                return false;
        }
        return true;
    }
};