위상정렬 — 진입차수 0 부터 처리한다

빌드 도구와 패키지 매니저는 실행 전에 같은 문제를 푼다. 의존 관계가 있는 작업들을 어떤 순서로 처리해야 모든 선행 작업이 끝난 뒤에 후속 작업이 시작되는가. 그래프 토픽을 정리하면서 이 문제의 표준 답인 위상정렬(Topological Sort)을 템플릿으로 만들었는데, 핵심 반복이 예상보다 단순했다. 의존성이 남지 않은 노드를 꺼내 처리하고, 그 노드에서 나가는 간선을 지운다. 이 반복만으로 순서가 나오고, 순서가 다 나오지 않으면 사이클이 있다는 뜻이다.

위상정렬은 방향 그래프에서 모든 간선 u → v 에 대해 u 가 v 보다 앞에 오도록 노드를 나열한다. 전제는 DAG(Directed Acyclic Graph, 유향 비순환 그래프)다. 사이클이 있으면 서로가 서로의 선행이 되어 만족하는 순서 자체가 존재하지 않는다.

Kahn BFS

Kahn BFS 는 진입차수(in-degree)를 기준으로 삼는다. 진입차수는 노드로 들어오는 간선 수, 즉 아직 처리되지 않은 선행 작업의 수다. 진입차수가 0 이면 의존성이 남지 않았으니 지금 처리해도 된다. 처리한 노드에서 나가는 간선을 지우면 이웃의 진입차수가 줄고, 0 이 된 이웃이 다음 처리 대상이 된다.

flowchart LR
    A["0"] --> B["1"]
    A --> C["2"]
    B --> D["3"]
    C --> D

위 그래프에서 진입차수 0 은 노드 0 뿐이다. 0 을 처리하면 1 과 2 의 진입차수가 0 이 되어 큐에 들어가고, 둘을 처리하면 3 이 이어진다. 결과는 [0, 1, 2, 3] 또는 [0, 2, 1, 3] — 진입차수 0 이 동시에 여럿이면 유효한 순서도 여럿이다.

from collections import defaultdict, deque


def topological_sort(n, edges):
    indegree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque(node for node in range(n) if indegree[node] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return order if len(order) == n else []

초기 큐에는 진입차수 0 인 노드를 전부 넣는다. 시작점이 하나라고 가정하고 첫 노드만 넣으면 독립된 컴포넌트를 놓친다. 모든 노드가 큐에 한 번, 모든 간선이 감소 연산에 한 번 관여하므로 복잡도는 O(V + E) 다. 꺼내는 순서에 우선순위가 필요하면(사전순으로 가장 앞선 결과 등) 큐를 heap 으로 바꾸면 된다.

사이클 검출

마지막 줄 len(order) == n 이 사이클 검출을 겸한다. 사이클 안의 노드들은 서로가 서로의 선행이라 어느 하나도 진입차수 0 에 도달하지 못한다. 큐가 비었는데 처리한 노드 수가 N 에 못 미치면, 남은 노드들은 사이클에 포함되어 있거나 사이클에 의존하고 있다. 별도의 방문 상태 추적 없이 개수 비교 하나로 판정이 끝난다.

Course Schedule(LeetCode 207)이 정확히 이 판정 문제다. 강의 N 개와 선수 관계가 주어지고 전부 수강할 수 있는지 묻는다. 위 골격에서 order 를 쌓는 대신 처리한 개수만 세고 개수가 N 과 같은지 반환하면 된다. 후속 문제 Course Schedule II(LeetCode 210)는 수강 순서 자체를 요구하는데, 같은 골격에서 반환을 order 로 바꾸면 끝이다.

두 문제에서 주의할 건 간선 방향이다. prerequisites[i] = [a, b] 는 “a 를 듣기 전에 b 를 먼저"라는 뜻이라 간선은 b → a 다. 방향을 반대로 만들면 진입차수 계산이 뒤집혀 오답이 된다. 문제 지문의 선후 관계를 간선 방향으로 옮길 때 이 유형에서 실수가 가장 자주 나온다.

DFS Post-order

위상정렬은 DFS 로도 만들 수 있다. 노드의 자식들을 모두 방문한 뒤에 자신을 결과에 추가하고, 순회가 끝나면 전체를 뒤집는다. 자식이 항상 자신보다 먼저 추가되므로 뒤집으면 선행이 앞에 온다.

사이클 검출은 방문 여부 boolean 만으로는 안 된다. 이미 방문한 노드를 다시 만났을 때 그것이 사이클인지, 다른 경로로 이미 처리를 끝낸 노드인지 boolean 은 구분하지 못해 사이클이 아닌 그래프를 사이클로 오판한다. 그래서 상태를 셋으로 나눈다. 미방문, 방문 중(현재 재귀 경로 안), 완료. 방문 중인 노드를 다시 만나면 사이클이고, 완료된 노드는 건너뛴다.

from collections import defaultdict


def topological_sort_dfs(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    UNVISITED, IN_PROGRESS, DONE = 0, 1, 2
    state = [UNVISITED] * n
    order = []

    def visit(u):
        if state[u] == IN_PROGRESS:
            return False
        if state[u] == DONE:
            return True
        state[u] = IN_PROGRESS
        for v in graph[u]:
            if not visit(v):
                return False
        state[u] = DONE
        order.append(u)
        return True

    for node in range(n):
        if state[node] == UNVISITED and not visit(node):
            return []
    return order[::-1]

재귀 깊이가 노드 수만큼 깊어질 수 있다. Python 은 기본 재귀 한도가 낮아 큰 그래프에서는 한도를 올리거나 반복형으로 바꿔야 한다.

선택 기준

항목	Kahn BFS	DFS post-order
진행 방식	진입차수 0 큐 반복	재귀 후 뒤집기
사이클 검출	처리 수 < N	3색 상태 추적
구현	반복문	재귀, 깊이 주의
꺼내는 순서 제어	큐를 heap 으로 교체	어색함

Kahn BFS 가 적합한 경우:

사이클 판정과 순서 산출을 한 골격으로 처리하고 싶다
재귀 없이 반복문으로 구현해 깊은 그래프에서도 안전하고 싶다
사전순 등 꺼내는 우선순위를 제어해야 한다

DFS post-order 가 적합한 경우:

이미 DFS 순회 코드가 있어 위상정렬까지 함께 얻으면 된다
사이클을 판정하는 데서 그치지 않고 사이클 경로 자체를 복원해야 한다
순회와 함께 다른 post-order 계산을 겸한다

빌드 도구가 타깃을 만들기 전에 의존성을 먼저 끝내는 것도, 패키지 매니저가 설치 순서를 정하는 것도 결국 같은 반복이다. 의존성이 남지 않은 노드부터 꺼내고, 꺼낸 만큼 이웃의 진입차수를 줄이고, 전부 꺼내지 못하면 순환 의존으로 판정한다. 진입차수 0 이라는 기준 하나로 순서와 사이클 판정이 같이 해결되는 게 이 템플릿을 정리하면서 가장 마음에 들었던 부분이다.

Kahn BFS#

사이클 검출#

DFS Post-order#

선택 기준#

Kahn BFS

사이클 검출

DFS Post-order

선택 기준