← 21주차 · 최단 경로와 위상 정렬
보통그래프위상 정렬

수강 과목 순서

과목 수 n과 선후 관계 목록 edges가 주어져요. 과목은 0번부터 n-1번까지 있고, edges의 각 원소 [a, b]는 'a를 들어야 b를 들을 수 있다'는 뜻이에요.

모든 선후 관계를 지키는 수강 순서를 배열로 반환해요. 가능한 순서가 여러 개면 번호가 작은 과목을 먼저 듣는 사전순으로 가장 앞선 하나를 반환해요. 순환이 있어 순서를 정할 수 없으면 빈 배열을 반환해요.

각 과목의 진입 차수(자기를 가리키는 간선 수)를 세고 0인 것부터 들어요. 하나 들을 때마다 그 과목이 여는 과목들의 진입 차수를 줄이고, 0이 되면 후보에 넣어요. 사전순을 위해 후보는 힙으로 관리해요.

예시

예시 1
입력
n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
출력
[0, 1, 2, 3]
설명
0을 먼저, 그다음 1·2, 마지막에 3이에요. 1과 2 중에서는 번호가 작은 1이 먼저예요.
예시 2
입력
n = 2, edges = [[0, 1], [1, 0]]
출력
[]
설명
서로가 서로의 선수과목이라 순서를 정할 수 없어요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ edges.length ≤ 200,000
  • 0 ≤ a, b < n
진입 차수 배열을 만들고 0인 과목을 최소 힙에 넣어요. 힙에서 가장 작은 번호를 꺼내 순서에 담고, 그 과목이 여는 과목들의 진입 차수를 줄여 0이 되면 힙에 넣어요. 다 끝났는데 담은 개수가 n보다 적으면 순환이 있으니 빈 배열을 반환해요.
javascript
class MinHeap {
  /** @param {(a: any, b: any) => number} [compare] 음수면 a가 먼저 나옵니다. */
  constructor(compare) {
    this.items = [];
    this.compare = compare ?? ((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  }
​
  get size() {
    return this.items.length;
  }
​
  peek() {
    return this.items.length > 0 ? this.items[0] : null;
  }
​
  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[parent], a[i]) <= 0) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }
​
  pop() {
    const a = this.items;
    if (a.length === 0) return null;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1;
        const r = l + 1;
        let small = i;
        if (l < a.length && this.compare(a[l], a[small]) < 0) small = l;
        if (r < a.length && this.compare(a[r], a[small]) < 0) small = r;
        if (small === i) break;
        [a[small], a[i]] = [a[i], a[small]];
        i = small;
      }
    }
    return top;
  }
}
​
function courseOrder(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);
  for (const [a, b] of edges) {
    graph[a].push(b);
    indegree[b]++;
  }
  const heap = new MinHeap();
  for (let v = 0; v < n; v++) if (indegree[v] === 0) heap.push(v);
  const order = [];
  while (heap.size > 0) {
    const v = heap.pop();
    order.push(v);
    for (const next of graph[v]) {
      if (--indegree[next] === 0) heap.push(next);
    }
  }
  return order.length < n ? [] : order;
}
이전 문제음수 간선이 있는 최단 경로
다음 문제모든 쌍 최단 거리
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.