Leetcode - 207. Course Schedule

문제

[강의, 사전수강필요 강의] 의 강좌 정보가 배열로 주어질때, 주어진 강좌를 모두 수강할 수 있는지 없는지 판단하라.

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Input: numCourses = 4, prerequisites = [[1,0],[2,1],[2,0],[3,2]]
Output: true
Input: numCourses = 2, prerequisites = [[0,2],[2,1],[1,0],[3,2]]
Output: false

아이디어 -> Topology Sort (위상정렬)

• adjacent[사전수강강의] 에 해당하는 강의 리스트를 자료구조를 생성하면 , 방향성 그래프 자료구조가 된다.
• 만약 그래프에 사이클이 존재한다면, 모든 강좌를 수강할 수 가 없다는 뜻이다.
• 따라서 해당 그래프의 사이클의 존재유무를 찾는게 이 문제가 요구하는것이다(해설참고함)

해결 DFS

is_cycle() 함수의 visited[] 값을 3가지로 정한게 참고한 답안. (이해하기가 쉽지 않았음.) 단순히 visited 체크된 값을 방문했을때 false를 해버리면 True도 false가 되어버린다(예시: TBD). 따라서 백트래킹으로 탐색할때, 이미 방문을 마친(이미 is_cycle() false 라서 사이클이 아님을 검증한) 노드는 2로 체크하여 굳이 다시 방문하지 않는다.

class Solution {
    vector<vector<int>> adj;
    bool is_cycle(vector<int> &vis, int cur) {
        /*
        vis 0: not visited
        vis 1: visited
        vis 2: no need to visit
        */
        if (vis[cur] == 1)
            return true;
        if (vis[cur] == 0) {
            vis[cur] = 1;
            for (int i = 0; i < adj[cur].size(); i++) {
                if (is_cycle(vis, adj[cur][i]))
                    return true;
            }
        }
        vis[cur] = 2;
        return false;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        adj = vector<vector<int>>(numCourses);
        vector<int> visites(numCourses, 0);
        
        for (auto it: prerequisites) {
            adj[it[1]].push_back(it[0]);
        }
        // 각 강좌들이 모두 연결되어있지 않을수도있기에, 모든 값을 순회한다.
        for (int i = 0; i < numCourses; i++) {
            if (is_cycle(visites, i))
                return false;
        }
        return true;
    }
};

해결 BFS

부모노드가 없는 노드 순서대로 BFS 탐색하면, 위상정렬된 순서가 나온다. 이것을 ret벡터에 저장하고, 만약 벡터의 크기가 주어진 강좌의 수와 다르다면 사이클이 존재한다는 의미.

class Solution {
    vector<vector<int>> adj;
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        adj = vector<vector<int>>(numCourses);
        unordered_map<int, int> indeg;
        vector<int> ret;
        // [1] -> [0]
        for (auto it: prerequisites) {
            adj[it[1]].push_back(it[0]);
            indeg[it[0]]++;
        }
        
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0)
                q.push(i);
        }
        while (!q.empty()) {
            int tgt = q.front();
            q.pop();
            ret.push_back(tgt);
            for (int i = 0; i < adj[tgt].size(); i++) {
                int adjval = adj[tgt][i];
                indeg[adjval]--;
                if (indeg[adjval] == 0)
                    q.push(adjval);
            }
        }
        if (ret.size() == numCourses)
            return true;
        return false;
    }
};