[LeetCode] C++ 207. Course Schedule

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

 

문제

 

문제 분석

- 순환(cycle)이 있는지 탐색하는 문제입니다. 사이클이 존재하면 false를 반환하고, 존재하지 않으면 true를 반환하여야 합니다.

- 현재 경로 중에서 중복되는 요소가 나온다면 false를 반환하면 됩니다. 이를 위해 set을 사용하였습니다.

- traced의 경우 탐색이 끝나고 제거를 해주어야 [0,1], [0,2], [1,2]와 같이 cycle이 아닌 경우를 제대로 판별할 수 있습니다. 0 -> 1 -> 2 경로 탐색 후 제거하지 않는다면 1 -> 2 탐색할 때 2를 이미 탐색한 노드로 판별하여 false를 반환하게 될 것 입니다.

- visited는 경로 탐색이 모두 끝난 요소에 대해서만 체크하게 하면서 가지치기로 경우의 수를 줄였습니다.

 

풀이

class Solution {
private:
    map<int, vector<int>> graph;
    vector<int> visited;
    set<int> traced;

    bool dfs(int start){
        if(traced.find(start) != traced.end()){
            return false;
        }

        if(find(visited.begin(), visited.end(), start) != visited.end()){
            return true;
        }

        traced.insert(start);

        for(const auto &node: graph[start]){
            if (!dfs(node)){
                return false;
            }
        }

        traced.erase(start);
        visited.push_back(start);

        return true;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for(const auto& prerequisite: prerequisites){
            graph[prerequisite[0]].push_back(prerequisite[1]);
        }

        for (const auto &node: graph){
            if (!dfs(node.first)){
                return false;
            }
        }

        return true;
    }
};