[LeetCode] BFS-DFS 207. Course Schedule (feat. 위상정렬(Topological Sort))

문제

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 true if you can finish all courses. Otherwise, return false.

 

Example 1:

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

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

---

문제풀이

- 이 문제는 Topological Sort(위상정렬)로 풀어야하는 문제 (선수과목 문제에 많이 사용함)

=> 위상정렬: 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘

=> 사이클이 없는 방향 그래프의 모든 노드를  => 방향성에 거스르지 않도록 순서대로 나열

 

- 위상정렬 알고리즘을 이해하려면 => indegree(진입차수)를 이해해야함

=> 진입차수(indegree): 특정한 노드로 들어오는 간선의 개수

=> 진출차수(outdegree): 특정한 노드에서 나가는 간선의 개수

 

- 위상정렬 알고리즘 수행과정

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   ① 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   ② 새롭게 진입차수가 0이 된 노드를 큐에 삽입

즉, 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과 => 여기선 order 배열이 그에 해당함

 

--------

 

- 정렬 결과(order), queue(위상정렬 시 indegree가 0인 노드를 넣을 곳), graph(key를 선행수업, value를 후행수업으로 하기), indegree(노드 개수만큼 생길 indegree들(화살표 갯수))

- prerequisites의 모든 선행 및 후행과목을 graph에 반영 => 반영하면서 후행과목에 숫자를 indegree의 index값으로 이용해서 해당 인덱스 값을 증가(indegree가 1개 생겼다는 뜻)

- indegree를 다 탐색해서 indegree[index] === 0 인 경우 => 큐에 넣는다

- 그 후 BFS로 정렬을 수행한다

=> graph에 queue에서 뺀값이 key로 있을 경우 => value값을 이용해서 indegree의 index로 활용하여 해당 index값을 하나 낮춰서 indegree를 없앤다(다음 정렬을 위해 없앤다)

=> 이 때 하나 낮춘값이 0이라면 즉시 queue에 담는다

=> 이 모든 과정을 한 후 => order(정렬의 결과값을 담는 배열)에다가 반영한다.

 

---

코드

위상정렬 문제는 Khan's Algorithm이 유명하다보니 BFS로 푸는 경우가 많다.

// BFS

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

  for (const [e, v] of prerequisites) {
    // build graph map
    if (graph.has(v)) {
      graph.get(v).push(e);
    } else {
      graph.set(v, [e]);
    }
    // build indegree array
    indegree[e]++;
  }

  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]--;
        if (indegree[e] === 0) queue.push(e);
      }
    }
    order.push(v);
  }

  return numCourses === order.length;
};

// DFS

function canFinish(numCourses, prerequisites) {
  const seen = new Set();
  const seeing = new Set();
  const adj = [...Array(numCourses)].map((r) => []);

  for (let [u, v] of prerequisites) {
    adj[v].push(u);
  }

  for (let c = 0; c < numCourses; c++) {
    if (!dfs(c)) {
      return false;
    }
  }
  return true;

  function dfs(v) {
    if (seen.has(v)) return true;
    if (seeing.has(v)) return false;

    seeing.add(v);
    for (let nv of adj[v]) {
      if (!dfs(nv)) {
        return false;
      }
    }
    seeing.delete(v);
    seen.add(v);
    return true;
  }
}

 

참고

[알고리즘] 위상 정렬 (Topological Sorting)