Leetcode - 210. Course Schedule II

문제

총 n개의 강좌 (0 ~ n-1)가 주어지고, 각각의 강좌는 사전수강 강좌가 있다. [강좌, 사전수강필요 강좌] 의 배열이 주어질때, 강좌를 수강해야할 순서대로 정렬하라. 만약 모든 강좌를 수강하는게 불가능하면 빈 vector를 리턴.

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

해결 아이디어 -> topological sort(위상정렬)

선후 관계가 정의된 그래프 구조상에서, 선후관계에 따라 순서를 정렬하는방법.

용어

• In-Degree(진입차수) : 특정 노드로 들어오는 간선 갯수
• Out-Degree(진출차수): 특정 노드에서 나가는 간선 갯수

알고리즘 BFS

1. 진입차수(In-degree)가 0인 노드를 큐에 push
2. 큐가 empty가 될때 까지 아래 반복
   a. 큐에서 pop한 노드의 나가는 간선 제거
   b. 새로 진입차수가 0이 된 노드 큐에 push

• 결과적으로 큐에서 pop한 노드의 순서가 Topology Sort된 순서.

구현

• 기본적으로 부모 노드가 없는 노드 순서로 정렬 하는것과 같다. 이것은 ->BFS로 풀수있다.
• 이를 거꾸로 하면 leaf노드 순서대로 정렬하고 반전하는것과 같다. 이것은 DFS로 해결할 수있다.

예시

예를 들어 [강좌, 사전강좌] 가 [1,0] [2,0] [3,1] [3,2] 로 주어질때

이를 그래프 자료구조로 표현하면

[0] -> 1 -> 2
[1] -> 3
[2] -> 3

진입차수(indegree)를 표현하면

[0] 0
[1] 1
[2] 1
[3] 2

해결 DFS

dfs순회하면서 leaf 노드 순서대로 저장.

class Solution {
    vector<vector<int>> graph;
    vector<int> ret;
    vector<int> visited;
    
    bool is_cycle(int cur) {
        if (visited[cur] == 1)
            return true;
        if (visited[cur] == 0) {
            visited[cur] = 1;
            for (int i = 0; i < graph[cur].size(); i++) {
                if (is_cycle(graph[cur][i]))
                    return true;
            }
            ret.push_back(cur); // leaf first order -> topological sort
        }
        visited[cur] = 2;            
        return false;
    }
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        graph = vector<vector<int>>(numCourses);
        visited = vector<int>(numCourses, 0);
        
        for (auto it: prerequisites) {
            graph[it[1]].push_back(it[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (is_cycle(i)) // if cycle exist, return an empty vector
                return {};
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

해결 BFS

진입차수가 0인 (부모노드가 없는) 노드 순서대로 저장.

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        unordered_map<int, int> indeg;
        vector<int> ret;
        
        for (auto it: prerequisites) {
            graph[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 < graph[tgt].size(); i++) {
                int adj = graph[tgt][i];
                indeg[adj]--;
                if (indeg[adj] == 0)
                    q.push(adj);
            }
        }
        if (ret.size() == numCourses)
            return ret;
        return {};
    }
};