[LeetCode] BFS 210. Course Schedule II (feat. 위상정렬)

문제

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

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.

---

코드

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */

function findOrder(numCourses, prerequisites) {
  const result = [];
  const queue = [];
  const graph = new Map();
  const indegree = Array(numCourses).fill(0);

  // graph 끼리의 모양 및
  // 진입차수의 갯수 적어야함(선행 => 후행)
  // 후행은 진입차수, 선행은 진출차수임
  for (const [e, v] of prerequisites) {
    // build graph map
    // key는 선행과목, value는 후행과목
    if (graph.has(v)) {
      graph.get(v).push(e);
    } else {
      graph.set(v, [e]);
    }
    // build indegree array
    indegree[e]++;
  }

  // indegree의 인덱스 값 = 진입차수를 받는 후행 과목의 이름
  for (let i = 0; i < indegree.length; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const v = queue.shift();
    if (graph.has(v)) {
      for (const e of graph.get(v)) {
        // 해당 과목의 진입차수를 끊고
        // 해당 진입차수를 받는 과목의 진입차수를 하나 낮춘다
        indegree[e]--;
        
        // 해당 과목의 진입차수가 0이면 
        // queue에 담아서 다시 위상정렬 시작
        if (indegree[e] === 0) queue.push(e);
      }
    }
    
    // graph.get(v)의 길이가 2 이상일 경우
    // 가장 뒤에 있을 수록 앞에 정렬될 수 있음
    result.push(v);
  }
        
  return result.length === numCourses ? result : []
}