위상 정렬

어떤 문제를 푸는가

작업들 사이에 "A를 끝내야 B를 시작할 수 있다" 같은 의존 관계 가 있을 때,
모든 의존을 어기지 않는 하나의 직선 순서 를 찾는 것이 위상 정렬입니다.
선수 과목 수강 순서, 빌드 의존성, 컴파일 순서 등이 대표 예입니다.

의존 관계를 방향 간선 \(u \to v\) ("u가 v보다 먼저")로 모으면 그래프가 됩니다.
위상 정렬이 가능하려면 이 그래프가 사이클이 없는 방향 그래프(DAG) 여야
합니다. 사이클이 있으면 순서를 정할 수 없습니다(서로 먼저여야 함).

방법 1 — 진입 차수 기반 (칸 알고리즘)

각 정점의 진입 차수(들어오는 간선 수)를 셉니다.

1. 진입 차수 0인 정점들을 큐에 넣는다 (선행 작업이 없는 것들).
2. 큐에서 하나 꺼내 결과에 추가하고, 그 정점에서 나가는 간선을 "제거"하며
   이웃의 진입 차수를 1씩 줄인다.
3. 새로 진입 차수가 0이 된 정점을 큐에 넣는다.
4. 큐가 빌 때까지 반복.

정당성: 진입 차수 0인 정점은 어떤 선행 조건도 없으므로 지금 처리해도
안전합니다. 그 정점을 빼면 다른 정점들의 선행 조건이 하나씩 줄고, 그렇게
의존이 하나씩 풀려 나갑니다.

방법 2 — DFS 후위 순서 뒤집기

각 정점에서 DFS를 돌고, 함수가 끝나는(자식을 다 본) 순서 로 스택에 쌓은
뒤 뒤집습니다. 자식이 모두 끝난 뒤 부모가 쌓이므로, 뒤집으면 부모가 앞섭니다.

사이클 탐지

칸 알고리즘에서 결과에 들어간 정점 수가 \(V\)보다 작으면 사이클이 있습니다.
사이클 위의 정점들은 진입 차수가 끝내 0이 되지 못해 큐에 못 들어가기 때문입니다.

복잡도

모든 간선과 정점을 상수 번 보므로 선형입니다.

답이 여러 개일 수 있다

진입 차수 0인 정점이 동시에 여러 개면 어느 것을 먼저 빼도 유효합니다. 따라서
위상 순서는 유일하지 않을 수 있습니다. "사전순으로 가장 빠른 순서" 같은
조건이 붙으면 큐 대신 우선순위 큐 를 씁니다. 다음 강의에서 구현과 응용을
봅니다.

칸 알고리즘 구현 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;        // u → v
        adj[u].push_back(v);
        indeg[v]++;
    }

    priority_queue<int, vector<int>, greater<>> pq;   // 사전순이면 최소 힙
    for (int v = 1; v <= n; v++)
        if (indeg[v] == 0) pq.push(v);

    vector<int> order;
    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) pq.push(v);
    }

    if ((int)order.size() != n) { cout << "사이클 존재\n"; return 0; }
    for (int v : order) cout << v << ' ';
    cout << '\n';
}

사전순 조건이 없으면 그냥 queue를 써도 됩니다. 우선순위 큐를 쓰면
\(O((V+E)\log V)\)로 살짝 늘어납니다.

파이썬 구현

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    indeg[v] += 1

q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

print("사이클 존재" if len(order) != n else ' '.join(map(str, order)))

흔한 함정

• 사이클 미검출 — order 크기를 \(V\)와 비교해 사이클을 반드시 확인하세요.
  사이클이 있는데 결과를 출력하면 오답입니다.
• 방향 혼동 — 간선 \(u \to v\)는 "u가 먼저"입니다. 문제의 의존 방향을
  뒤집어 입력하지 않도록 주의.
• 진입 차수 갱신 시점 — --indeg[v] == 0일 때만 큐에 넣어야 중복 추가를
  막습니다.

DAG 위에서의 DP — 위상 정렬의 진짜 힘

위상 순서대로 정점을 처리하면, 어떤 정점을 볼 때 그 정점으로 오는 모든
정점은 이미 처리되어 있습니다. 그래서 DAG 위의 최장 경로, 경로 수 세기,
누적 비용 같은 DP를 한 번의 순회로 깔끔하게 계산합니다.

// DAG 최장 경로 (모든 시작점)
for (int u : order)
    for (int v : adj[u])
        dp[v] = max(dp[v], dp[u] + 1);

일반 그래프의 최장 경로는 NP-난해지만, DAG에서는 위상 정렬 덕분에 선형
시간 에 풀린다는 점이 핵심입니다.

응용 패턴

• 선수 과목 / 빌드 순서 — 그대로 위상 정렬.
• 사이클 판정 — "순서를 매길 수 있는가"가 곧 "DAG인가".
• DAG 경로 수 / 최장·최단 경로 — 위상 순서 DP.
• 사전순 최소 위상 순서 — 우선순위 큐.

"의존을 어기지 않는 순서"가 필요하면 위상 정렬, 그 순서 위에서 DP를 얹으면
의존 있는 계산이 단번에 풀립니다.

출제 신호

위상 정렬은 문장 신호가 또렷합니다.

• "\(A\)를 먼저 해야 \(B\)를 할 수 있다" — 선수 과목, 건물 건설 순서, 작업 의존성
• "키 비교 결과들이 주어질 때 줄 세우기", "일부 쌍의 순서만 알 때 가능한 나열"
• "모든 작업을 끝내는 최소 시간" (의존성 + 소요 시간 → 위상 순서로 DP)
• "순서가 모순인지(사이클) 판정하라"

그래프가 방향이고 사이클이 없어야(DAG) 한다는 게 전제입니다. 문제가
사이클 가능성을 열어 두었다면 "불가능 판정"까지가 과제에 포함된 것입니다.
\(V, E \le 10^5{\sim}10^6\)에서도 \(O(V + E)\)라 규모 부담이 없습니다.

풀이 결정 절차

1. 문장 속 "먼저/이후/의존" 관계를 간선 방향으로 번역합니다 — "A 먼저, B 나중"은
   \(A \to B\), 그리고 indeg[B]++.
2. 출력 요구를 확인합니다 — (a) 아무 위상 순서나 하나, (b) 사전순 최소
   (큐를 최소 힙으로 교체, \(O(E \log V)\)), © 순서가 유일한지 판정
   (큐 크기가 항상 1인지 확인).
3. 위에 DP가 얹히는지 봅니다 — "최소 완료 시간"은
   time[v] = max(time[u] for u→v) + cost[v]를 위상 순서대로 계산합니다.
   max를 빼먹고 마지막 부모만 반영하는 실수가 흔합니다.
4. 사이클 판정 방법을 정합니다 — 결과에 담긴 정점 수가 \(V\) 미만이면 사이클.

자주 하는 실수

• 사이클 판정 누락 — 큐가 비어도 모든 정점을 처리했다는 보장이 없습니다.

from collections import deque

q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

if len(order) < n:        # 처리 못 한 정점 = 사이클에 갇힌 정점
    print(-1)

• 간선 방향 반대로 — "B는 A 이후"를 \(B \to A\)로 넣는 번역 실수. 작은
  예제로 순서가 뒤집혀 나오면 십중팔구 이것입니다.
• indeg 0 정점을 시작에 전부 넣지 않음 — 시작점이 하나라고 가정하면
  여러 컴포넌트가 있는 입력에서 틀립니다.
• 중복 간선 — 같은 의존이 두 번 주어지면 indeg가 2 올라갑니다. 문제에
  따라 중복 제거가 필요한지 확인하세요.
• 사전순 요구를 못 보고 deque 사용 — "여러 답 중 사전순으로 가장 빠른
  것"이라는 문장이 있으면 heapq로 바꿔야 합니다.
• DP 변형에서 max 대신 마지막 갱신값 사용 — 완료 시간은 모든 선행
  작업의 최댓값 기준입니다. time[v] = max(time[v], time[u] + cost[v]).

연습 방법

사이드바 연습 목록의 기본 줄 세우기 문제로 큐 기반 칸(Kahn) 구현을 익히고,
사전순 최소(힙 교체) → 완료 시간 DP(건물 짓기류) → 유일성 판정 순서로
확장하세요. 문제를 읽으며 "무엇이 정점이고, '먼저'가 어느 방향 간선인가"를
한 줄로 적고 시작하는 습관이 번역 실수를 막아 줍니다. 태그된 문제
3문제 이상 해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.