topological sorting이란 무엇인가요?

Question

Accepted Answer

**Topological sort(위상 정렬)**는 **DAG**(방향 비순환 그래프)의 정점을 선형으로 정렬하여 모든 간선 u->v에서 u가 v보다 **앞에** 오도록 합니다. "이 작업들을 그 의존성을 고려할 때 어떤 순서로 할 수 있는가?"에 답합니다.

## 개념

흔한 두 가지 접근: **Kahn 알고리즘**(in-degree가 0인 노드를 반복적으로 제거) 또는 **DFS**(역 후위 순서). 유효한 정렬은 **사이클이 없을 때만** 존재합니다.

## 예시 (Kahn 알고리즘)

```python
from collections import deque

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                 # 들어오는 간선 수 세기
    queue = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                 # 간선 "제거"
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> 사이클

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## 복잡도

- **시간:** O(V + E). **공간:** O(V).

## 언제 사용하나 / 함정

**빌드 시스템**, 작업 스케줄링, 강의 선수 과목, 의존성 해결에 사용하세요. 결과가 V보다 짧으면 그래프에 **사이클**이 있습니다(유효한 순서 없음). 정렬은 일반적으로 **유일하지 않습니다**.

## 왜 중요한가

의존성 정렬은 어디에나 있습니다 — 컴파일러, 패키지 관리자, 스프레드시트 재계산, CI 파이프라인.

Topological sort는 방향 그래프의 사이클 탐지 역할도 겸합니다.

문제를 "제약 하의 순서 정하기"로 인식하고 topo sort로 손을 뻗는 것은 강력한 시니어 신호입니다.