위상 정렬 쉽게 이해하기: 동작 원리, 코드, 시간 복잡도

위상 정렬이 해결하는 문제

현실의 많은 작업에는 선행 조건이 있습니다. 과목에는 선수 과목이 있고, 소스 파일은 import하는 파일 뒤에 컴파일해야 하며, 패키지는 의존하는 패키지 뒤에 설치해야 하고, 스프레드시트 셀은 참조하는 셀 뒤에 계산해야 합니다. 각 작업을 노드로, "먼저 해야 한다"는 각 규칙을 방향 간선으로 그립니다. 위상 순서는 모든 간선을 지키는 작업 나열입니다.

순서는 그래프에 방향 사이클이 없을 때, 그리고 그때에만 존재합니다. A가 B를 필요로 하고 B가 A를 필요로 하면 유효한 순서는 없으며, 좋은 위상 정렬은 무한 루프를 돌지 않고 이를 보고합니다. DAG에는 보통 유효한 순서가 여러 개 있으며 알고리즘은 그중 하나를 반환합니다.

핵심 아이디어

칸의 알고리즘(1962년 아서 칸(Arthur Kahn)이 발표)은 앞쪽에서부터 작동합니다.

1. 모든 노드의 들어오는 간선 수(진입 차수)를 셉니다.
2. 진입 차수가 0인 노드를 모두 큐에 넣습니다. 이 작업들은 아직 충족되지 않은 선행 조건이 없습니다.
3. 큐에서 노드를 꺼내 결과에 추가합니다. 그 노드에서 나가는 각 간선에 대해 대상의 진입 차수를 1 줄이고, 0이 되면 대상을 큐에 넣습니다.
4. 큐가 비었을 때 결과에 모든 노드가 들어 있으면 그것이 위상 순서입니다. 그렇지 않다면 남은 노드는 사이클의 일부입니다.

DFS 방식은 뒤쪽에서부터 작동합니다. 노드는 자신이 가리키는 모든 노드가 끝난 뒤에야 끝나므로, 종료 순서의 역순으로 나열하면 각 노드가 자신의 모든 후속 노드보다 앞에 놓입니다.

단계별 예제

옷 입기: underwear → pants, pants → shoes, socks → shoes, pants → belt, shirt → belt, shirt → tie, tie → jacket, belt → jacket. 큐의 노드를 선입선출 순서로 꺼내는 칸의 알고리즘입니다.

최종 순서: underwear, socks, shirt, pants, tie, shoes, belt, jacket. 8개 노드가 모두 배치되었으므로 사이클은 없습니다.

파이썬 구현

deque를 사용한 칸의 알고리즘입니다.

from collections import deque
def topo_sort(graph):
    """graph: dict node -> list of nodes that must come after it."""
    indegree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            indegree[m] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for m in graph[n]:
            indegree[m] -= 1
            if indegree[m] == 0:
                queue.append(m)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order
dress = {
    "underwear": ["pants"], "socks": ["shoes"], "shirt": ["belt", "tie"],
    "pants": ["shoes", "belt"], "tie": ["jacket"], "belt": ["jacket"],
    "shoes": [], "jacket": [],
}
print(topo_sort(dress))
# ['underwear', 'socks', 'shirt', 'pants', 'tie', 'shoes', 'belt', 'jacket']

DFS 버전은 후속 노드가 모두 끝난 뒤에 노드를 추가하고 마지막에 리스트를 뒤집습니다.

def topo_sort_dfs(graph):
    order, state = [], {}             # state: 1 = in progress, 2 = done
    def visit(n):
        if state.get(n) == 1:
            raise ValueError("graph has a cycle")
        if state.get(n) == 2:
            return
        state[n] = 1
        for m in graph[n]:
            visit(m)
        state[n] = 2
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]
print(topo_sort_dfs(dress))
# ['shirt', 'tie', 'socks', 'underwear', 'pants', 'belt', 'jacket', 'shoes']

두 결과 모두 유효합니다. 파이썬 3.9부터는 표준 라이브러리에 graphlib.TopologicalSorter도 있습니다. 위의 딕셔너리들과 반대로 각 노드를 그 선행 노드에 대응시키는 매핑을 받는다는 점에 유의하세요.

from graphlib import TopologicalSorter
ts = TopologicalSorter({"b": {"a"}, "c": {"a", "b"}})   # node: its prerequisites
print(list(ts.static_order()))  # ['a', 'b', 'c']

시간 복잡도와 공간 복잡도

변형과 흔한 실수

• 가장 작은 순서 우선: 큐 대신 최소 힙(heapq)을 써서 항상 선택 가능한 가장 작은 노드를 고릅니다. O((V + E) log V)에 사전순으로 가장 앞서는 순서를 얻습니다.
• 병렬 스케줄링: 칸의 알고리즘을 라운드 단위로 처리하여 진입 차수 0인 노드를 한꺼번에 꺼냅니다. 각 라운드는 동시에 실행할 수 있는 작업 묶음이며, 라운드 수는 가장 긴 의존 체인의 길이입니다. graphlib.TopologicalSorter는 get_ready()와 done()으로 이를 지원합니다.
• DAG에서 가장 긴 경로 또는 가장 짧은 경로: 위상 순서대로 간선을 완화하면 음수 가중치가 있어도 O(V + E)에 답을 얻습니다.
• 서로 다른 순서의 개수를 세는 것은 훨씬 어려운 문제입니다. 큰 그래프에서 모든 순서를 나열하려 하지 마세요.

재귀 DFS 버전에는 파이썬의 모든 재귀 DFS와 같은 재귀 한도 문제가 있습니다. 수천 개 노드의 체인에는 칸의 알고리즘을 사용하세요.

언제 쓰는지와 실제 활용

• Make 같은 빌드 도구는 의존성에 따라 타깃 순서를 정하고, 패키지 관리자는 의존성 그래프로 설치 순서를 정합니다.
• 스프레드시트는 의존 순서대로 셀을 다시 계산하고 순환 참조를 알려 줍니다.
• 작업 스케줄러와 워크플로 엔진, 예를 들어 DAG 기반 데이터 파이프라인은 위상 순서로 작업을 실행합니다.
• 컴파일러는 선언 순서를 정하고 식 그래프를 평가하며, 데이터베이스는 외래 키의 생성 및 삭제 순서를 정합니다.
• 코딩 인터뷰 문제: 수강 신청 순서 I과 II, 외계인 사전(정렬된 단어에서 문자 순서 추론), 병렬 수업, 빌드 계획의 최소 높이.