16강: 위상 정렬

이 강의에서 배우는 것

• 1Kahn's 알고리즘(BFS 기반)으로 위상 정렬을 구현한다.
• 2DFS 기반 위상 정렬에서 후위 순서의 역이 위상 순서임을 이해한다.
• 3위상 정렬로 사이클 탐지와 유일한 순서 판별을 수행한다.

개요

소개: DAG와 선후 관계

위상 정렬(Topological Sort)은 **방향 비순환 그래프(DAG)** 에서 모든 선후 관계를 만족하는 노드의 순서를 결정합니다.

**등장하는 문제 유형:**

핵심 개념

진입 차수 (In-degree)

그래프:
  1 → 3
  2 → 3
  3 → 4 → 5
  2 → 5

진입 차수:
  1: 0 (아무것도 1을 가리키지 않음)
  2: 0
  3: 2 (1과 2가 가리킴)
  4: 1
  5: 2

Kahn's 알고리즘 (BFS 기반)

1. 진입 차수가 0인 모든 노드를 큐에 삽입
2. 큐에서 노드를 꺼내 결과에 추가
3. 해당 노드의 모든 인접 노드의 진입 차수 -1
4. 진입 차수가 0이 된 노드를 큐에 삽입
5. 큐가 빌 때까지 반복
6. 결과 길이 < V 이면 사이클 존재

시뮬레이션:
  in-degree: {1:0, 2:0, 3:2, 4:1, 5:2}
  큐: [1, 2]
  → pop(1): 결과=[1], 3의 in-degree=1
  큐: [2]
  → pop(2): 결과=[1,2], 3의 in-degree=0, 5의 in-degree=1
  큐: [3]
  → pop(3): 결과=[1,2,3], 4의 in-degree=0
  큐: [4]
  → pop(4): 결과=[1,2,3,4], 5의 in-degree=0
  큐: [5]
  → pop(5): 결과=[1,2,3,4,5]  ← 완료

위상 정렬 다이어그램

DAG (Directed Acyclic Graph):
  1 ──→ 3 ──→ 5
  2 ──→ 3
  2 ──→ 4 ──→ 5

가능한 위상 순서:
  [1, 2, 3, 4, 5]
  [1, 2, 4, 3, 5]
  [2, 1, 3, 4, 5]
  [2, 4, 1, 3, 5]
  ... (여러 개 가능)

유일한 위상 순서: 큐에 항상 1개만 있을 때

시간/공간 복잡도

• 시간: **O(V + E)**
• 공간: **O(V)** — in-degree 배열 + 큐

예제로 보기

자주 하는 실수 5가지

1. **방향 없는 그래프에 위상 정렬 적용** - 위상 정렬은 **방향 그래프**에만 적용 가능 - 무방향이면 모든 간선이 "양방향"이라 사이클로 간주됨
2. **사이클 체크 없이 결과를 신뢰** ```python result = kahns_sort(graph) # 사이클이 있으면 result 길이 < V if len(result) < n: print("사이클 존재!") ```
3. **in-degree 배열 크기를 n+1이 아닌 n으로 설정** - 1-indexed: `in_degree = [0] * (n + 1)`
4. **간선 추가 시 in-degree 업데이트 누락** ```python graph[u].append(v) in_degree[v] += 1 # ← 반드시 같이 ```
5. **우선순위 큐 없이 사전순 최소 위상 정렬 구현** - 사전순 최소 위상 정렬이 필요하면 `heapq` (최소 힙) 사용 - 일반 큐(deque)는 삽입 순서만 보장

정리

직접 해 보기

1. 5개 과목 `[A→C, B→C, C→D, B→D]` 의 수강 가능 순서를 구하세요.
2. `[1→2, 2→3, 3→1]` 에 위상 정렬을 적용하면 어떻게 되나요?
3. 유일한 위상 순서가 존재하는 그래프의 예를 만들어 보세요.

과제

`homework/README.md` 참조