위상정렬

작업 4개와 선행 관계 3개를 손으로 따라가 봅니다. 0 → 1, 2 → 1, 1 → 3 (화살표는 "먼저 → 나중").

시작할 때 각 작업의 진입 차수(자기 앞에 걸린 선행 작업의 수)는 [0, 2, 0, 1]입니다. 0번과 2번은 앞에 아무것도 없으므로 대기열에서 출발합니다.

작업 4개가 모두 결과에 담겼으므로 사이클이 없고, [0, 2, 1, 3]은 유효한 실행 순서입니다. 만약 3 → 0 간선이 하나 더 있었다면 처음부터 진입 차수 0인 작업이 없어 결과가 비고, 그것이 곧 "불가능" 판정입니다.

표준 구현은 Kahn's algorithm (BFS 기반)입니다. 위 표의 과정을 그대로 코드로 옮깁니다.

1. 진입 차수를 셉니다 — 화살표가 도착하는 쪽에 +1 합니다.

for (const [from, to] of edges) {
  adj[from].push(to);
  indeg[to]++;
}

2. 진입 차수 0인 작업을 전부 대기열에 넣습니다 — 시작점이 여럿일 수 있고, 간선이 하나도 없는 고립 노드도 여기 포함됩니다.

for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);

3. 하나 꺼내 확정하고, 그 작업이 가리키던 이웃들의 대기 개수를 줄입니다. 0이 되면 새로 대기열에 넣습니다.

const cur = queue[head++];
order.push(cur);
for (const next of adj[cur]) {
  if (--indeg[next] === 0) queue.push(next);
}

4. 마지막에 개수를 확인합니다 — 전부 담기지 못했다면 남은 작업들이 서로를 기다리는 사이클입니다.

return order.length === n ? order : [];

전체 코드:

function topoSort(n: number, edges: number[][]): number[] {
  const adj: number[][] = Array.from({ length: n }, () => []);
  const indeg = Array(n).fill(0);
  for (const [from, to] of edges) {
    adj[from].push(to);
    indeg[to]++;                          // ① 진입 차수 세기
  }
  const queue: number[] = [];
  let head = 0;
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i); // ② 시작점
  const order: number[] = [];
  while (head < queue.length) {
    const cur = queue[head++];
    order.push(cur);                      // ③ 확정
    for (const next of adj[cur]) {
      if (--indeg[next] === 0) queue.push(next); // ④ 선행 해소 → 진입
    }
  }
  return order.length === n ? order : []; // ⑤ 전부 못 담으면 사이클
}

⑤가 중요합니다: order.length < n이면 사이클 존재 — "불가능" 판정 문제의 정답 조건입니다.

문제 지문에 "선수 과목", "먼저 완료해야", "의존 관계", "빌드 순서" 같은 말이 나오면 위상정렬입니다. 격자가 아닌 관계 그래프 + 순서라는 조합이 신호입니다.

• 작업 목록과 "A는 B보다 먼저"라는 쌍들이 입력으로 주어진다 → 그대로 간선입니다.
• "가능한 순서를 아무거나 출력하라", "불가능하면 -1" → 사이클 판정까지 요구하는 전형입니다.
• 대표 상황: 강의 수강 계획(선수 과목), 패키지 설치 순서(의존성), 공정 라인의 작업 스케줄링.

• 가능한 순서 하나 출력 — 위 코드 그대로
• 최소 소요 시간 (병렬 수행 가능): 레벨 단위 BFS로 층 수를 세거나, time[next] = max(time[next], time[cur] + cost[next])
• 사전순으로 가장 빠른 순서: 큐 대신 최소 힙 사용
• 진입 차수가 0인 노드가 동시에 여럿 = 그 작업들은 병렬 가능

// 최소 소요 시간 — ③④ 자리에서 누적 시간을 함께 갱신
const time = Array(n).fill(0);
for (const next of adj[cur]) {
  time[next] = Math.max(time[next], time[cur] + cost[next]);
  if (--indeg[next] === 0) queue.push(next);
}

• 진입 차수를 indeg[from]++로 반대로 셈 — 화살표의 도착지에 +1

indeg[from]++;  // 잘못 — 출발지를 세면 시작점이 사라집니다
indeg[to]++;    // 올바름 — 나를 막고 있는 선행 작업의 수

• ⑤ 사이클 검사 생략 — "불가능한 경우 빈 배열/-1" 요구를 놓침
• shift()로 큐 구현 — head 인덱스로 (큐 토픽 참고)

const cur = queue.shift()!;   // 매번 O(N) — 노드가 많으면 시간 초과
const cur = queue[head++];    // O(1)

• 간선이 없는 고립 노드 누락 — 진입 차수 0이므로 처음부터 큐에 들어가야 함

• 복잡도: 각 노드를 정확히 한 번 꺼내고 각 간선을 정확히 한 번 훑으므로 O(V + E)입니다. 인접 리스트를 쓰는 한 노드 수가 아무리 많아도 간선 수에 비례하는 비용만 듭니다.
• DFS 기반 구현: 각 노드를 깊이 우선으로 방문하고, 되돌아 나오는 순간(후위) 스택에 담은 뒤 마지막에 뒤집으면 위상 순서가 됩니다. 이때 사이클은 "방문 중" 표시가 붙은 노드를 다시 만나는 것으로 감지합니다. Kahn 방식보다 상태 관리가 까다로워 코테에서는 BFS 쪽이 안전합니다.
• 순서의 유일성 판정: 매 단계에서 대기열 크기가 항상 1이었다면 가능한 순서가 딱 하나뿐이라는 뜻입니다. "순서가 유일하게 결정되는가"를 묻는 변형은 이 조건을 확인합니다.
• 사전순 최소 순서의 비용: 최소 힙을 쓰면 꺼내고 넣는 데 log가 붙어 O(V log V + E)가 됩니다. 사전순 요구가 없다면 굳이 힙을 쓰지 않습니다.
• DAG 위의 DP: 위상 순서대로 훑으면 "이미 앞의 값이 확정된 상태"가 보장되므로, 사이클 없는 그래프의 최장 경로·경로 개수 같은 DP를 한 번의 순회로 계산할 수 있습니다. 최소 소요 시간 변형이 바로 이 형태입니다.

시각화로 "진입 차수 0 → 처리 → 잠금 해제"의 흐름을 본 뒤, 기본 순서 출력 → 최소 시간 → 사이클 판정 순으로 푸세요. BFS(큐)가 선수 지식입니다.