순서 제약 문제 풀이: 위상 정렬을 언제 써야 할까

이 글의 목차 숨기기

위상 정렬은 어떤 문제를 푸는 도구일까

왜 그래프 문제로 바뀌는가

진입차수는 왜 중요할까

왜 queue가 자연스럽게 연결될까

문제에서 어떤 신호가 보이면 위상 정렬일까

사이클이 있으면 왜 문제가 될까

자주 하는 실수

마무리

순서 제약 문제 풀이: 위상 정렬을 언제 써야 할까 — 어떤 일을 하기 전에 먼저 끝나야 할 일이 있다면 위상 정렬을 의심해볼 수 있다

위상 정렬은 그래프 알고리즘을 배웠어도 실제 문제에서 잘 안 떠오르는 경우가 많습니다. 이유는 문제에 “위상 정렬을 하세요”라고 적혀 있지 않고, 대신 선수 과목, 빌드 순서, 작업 의존성처럼 일상적인 말로 순서 제약을 설명하기 때문입니다.

이번 글에서는 위상 정렬을 공식으로 외우는 대신, 어떤 일을 하기 전에 먼저 끝나야 할 일이 있는 문제로 읽는 감각을 중심으로 설명하겠습니다.

순서 제약 문제 풀이 요약 카드 — 핵심 판단 기준을 먼저 잡는 요약 카드

위상 정렬은 어떤 문제를 푸는 도구일까

위상 정렬은 순서 제약이 있는 문제를 푸는 도구입니다. 즉 A를 하기 전에 B가 먼저 되어야 하고, C를 하기 전에 A가 먼저 되어야 한다면 이런 선후관계를 만족하는 전체 순서를 만드는 문제에 잘 맞습니다.

대표적으로 선수 과목 문제, 작업 스케줄링, 빌드 의존성, 선행 조건이 있는 게임/퀘스트 순서 문제에서 자주 등장합니다.

왜 그래프 문제로 바뀌는가

A를 하기 전에 B가 먼저여야 한다는 말은, 그래프에서는 보통 B → A 간선으로 표현할 수 있습니다. 즉 먼저 해야 하는 쪽에서 나중에 할 쪽으로 방향을 그립니다.

이렇게 하면 문제의 핵심은 결국 “방향 그래프에서 선후관계를 깨지 않는 순서를 만들 수 있는가”로 바뀝니다. 그래서 위상 정렬은 방향 그래프 문제로 다뤄집니다.

진입차수는 왜 중요할까

진입차수는 어떤 정점으로 들어오는 간선 수입니다. 즉 그 일을 시작하기 전에 아직 남아 있는 선행 조건 개수라고 생각하면 됩니다.

진입차수가 0이라는 것은, 지금 당장 시작해도 되는 일이라는 뜻입니다. 그래서 위상 정렬에서는 진입차수 0인 정점부터 queue에 넣고 처리합니다.

입문자가 많이 헷갈리는 부분은 진입차수를 단순한 그래프 숫자로만 보는 것입니다. 실제로는 “아직 풀리지 않은 선행 조건 수”라고 해석하는 편이 훨씬 이해가 쉽습니다. 이렇게 바꾸면 queue에 들어가는 순간도 자연스럽게 이해됩니다.

from collections import deque

def topo_sort(graph, indegree, n):
    q = deque([i for i in range(n) if indegree[i] == 0])
    order = []

    while q:
        cur = q.popleft()
        order.append(cur)
        for nxt in graph[cur]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

    return order

from collections import deque

def topo_sort(graph, indegree, n):
    q = deque([i for i in range(n) if indegree[i] == 0])
    order = []

    while q:
        cur = q.popleft()
        order.append(cur)
        for nxt in graph[cur]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

    return order