위상 정렬이란 무엇인가요?

위상 정렬을 어떻게 구현하나요?

대표적인 방법이 두 가지입니다. Kahn's algorithm(BFS 기반)과 DFS 기반입니다.

Kahn's algorithm:

모든 노드의 진입차수(들어오는 간선 수)를 계산합니다.
진입차수가 0인 노드를 큐에 넣습니다.
큐에서 노드를 꺼내 결과에 추가하고, 해당 노드의 이웃 노드의 진입차수를 1 줄입니다.
진입차수가 0이 된 이웃을 큐에 넣습니다.
큐가 빌 때까지 반복합니다. 결과의 노드 수가 전체보다 작으면 사이클이 있습니다.

from collections import deque
 
def topological_sort(graph, n):
    indegree = [0] * n
    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1
 
    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []
 
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
 
    return result if len(result) == n else []  # 빈 리스트면 사이클 있음

DFS 기반: DFS로 모든 노드를 탐색하고, 현재 노드에서 더 이상 갈 곳이 없으면 스택에 쌓습니다. 탐색 완료 후 스택에서 순서대로 꺼내면 위상 정렬 순서입니다.

두 방법 모두 O(V + E)입니다. Kahn's algorithm이 사이클 감지가 직관적이라 코딩테스트에서 더 자주 씁니다.

사이클이 있으면 위상 정렬을 할 수 없는 이유는?

A → B → C → A처럼 사이클이 있으면 A가 C보다 앞에 와야 하고, C가 B보다 앞에 와야 하고, B가 A보다 앞에 와야 하는데 동시에 만족할 수 없습니다.

실무에서 사이클은 순환 의존성 문제로 나타납니다. A 모듈이 B를 import하고, B가 다시 A를 import하면 어느 쪽을 먼저 로드해야 할지 알 수 없습니다. Node.js는 이 경우 한쪽이 빈 객체를 받게 되는 문제가 생기고, Python은 ImportError가 납니다.

패키지 관리자도 마찬가지입니다. npm이 설치 순서를 결정하다 순환 의존성을 발견하면 경고를 냅니다. 이런 순환이 생기면 의존성 구조 자체를 바꿔야 합니다.

Kahn's algorithm으로 사이클을 감지할 수 있습니다. 위상 정렬 결과의 노드 수가 전체 노드 수보다 작으면 큐에 들어가지 못한 노드가 있다는 의미이고, 그 노드들이 사이클을 이루고 있습니다.

위상 정렬이 실제로 쓰이는 곳은?

빌드 시스템, 패키지 의존성, 작업 스케줄링, 데이터 파이프라인 등에서 씁니다.

빌드 시스템: A.cpp가 B.h를 include하면 B를 먼저 컴파일해야 합니다. Make, Gradle, Bazel이 의존성 그래프에서 위상 정렬로 빌드 순서를 결정합니다.
패키지 설치: npm install은 package.json의 의존성 트리를 위상 정렬해 설치 순서를 구합니다. 의존하는 패키지를 먼저 설치합니다.
데이터 파이프라인: Airflow, dbt 같은 도구에서 태스크 간 의존성을 DAG로 정의하고 위상 정렬로 실행 순서를 결정합니다.
대학 수강 신청: 선수과목 조건이 있는 과목 이수 순서를 결정하는 문제도 위상 정렬로 풀 수 있습니다.