[leetcode 210] Course Schedule II

There are a total of n courses you have to take labelled from 0 to n - 1.

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

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].

Example 3:

Input: numCourses = 1, prerequisites = [] Output: [0]

 

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

문제 풀이

dfs/bfs를 사용하고 topological sort를 사용한다. 

 

indegree(노드로 향하는 엣지)수를 세는 것이 포인트이다.

indegree가 0이라면 그래프의 출발지라는 뜻이다. indegree가 0인 노드만 큐에 푸쉬하여 그래프의 전체 노드를 순회할 수 있는지 체크한다.

 

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
       if(numCourses == 1){
           return {0};
       }
        
        vector<int> result;
        
        vector<int> v[numCourses];
        vector<int> cnt(numCourses,0);
        for(int i=0; i<prerequisites.size(); i++){
            v[prerequisites[i][1]].push_back(prerequisites[i][0]);
            cnt[prerequisites[i][0]]++;
        }
        
        queue<int> q;
        
        for(int i=0;i<numCourses; i++){
            if(cnt[i] == 0){
                q.push(i);
            }
        }
        
        while(!q.empty()){
            int fr = q.front();
            q.pop();
            
            result.push_back(fr);
            
            for(int i=0; i<v[fr].size(); i++){
                cnt[v[fr][i]]--;
                
                if(cnt[v[fr][i]] == 0){
                    q.push(v[fr][i]);
                }
            }
        }
        
        if(result.size() != numCourses){
            return {};
        }
        return result;
    }
};

 

++java로는 이중 벡터 선언을 어떻게 하는지 알고 싶어서 자바로도 코딩해봤다. 자바에선 맵을 사용하여 직접 integer와 list를 매핑해줘야한다.

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        
        int[] indegree = new int[numCourses];
        int[] result = new int[numCourses];
        
        for(int i=0; i<prerequisites.length; i++){
            int dst = prerequisites[i][0];
            int src = prerequisites[i][1];
            
            List<Integer> lst = adjList.getOrDefault(src, new ArrayList<Integer>());
            lst.add(dst);
            adjList.put(src, lst);
            
            indegree[dst]+=1;
        }
        
        Queue<Integer> q = new LinkedList<>();
        
        for(int i=0; i<numCourses; i++){
            if(indegree[i]==0){
                q.add(i);
            }
        }
        
        int sze = 0;
        while(!q.isEmpty()){
            int node = q.remove();
            result[sze++] = node;
            
            if(adjList.containsKey(node)){
                for(Integer nigh: adjList.get(node)){
                    indegree[nigh]--;
                    
                    if(indegree[nigh]==0){
                        q.add(nigh);
                    }
                }
            }
            
        }
        
        if(sze == numCourses){
            return result;
        }
        return new int[0];
    }
}