많은 사람이 위상 정렬 알고리즘 자체는 안다. BFS 기반 Kahn's 알고리즘이든 DFS 후처리든, 구현은 외우면 된다. 진짜 문제는 "이 문제가 위상 정렬이네"를 알아채는 순간이다. 그 감각이 없으면 구현력이 아무리 좋아도 30분을 날린다.

어디서 튀어나오나

코테에서 위상 정렬은 대놓고 "순서를 구하라"고 나오지 않는다. 이런 식이다:

  • "수강해야 할 과목 순서를 정하시오" (Course Schedule 류)

  • "A 작업이 끝나야 B를 시작할 수 있다" (프로젝트 스케줄링)

  • "사전에서 알파벳 순서를 유추하시오" (외계어 사전)

  • "빌드 의존성 순서를 결정하시오"

공통점이 뭐냐면 — 선후 관계(방향 간선)가 있고, 사이클이 없어야 하며, 전체 순서를 결정해야 한다. 이 세 조건이 보이면 DAG(방향 비순환 그래프) 위의 정렬 문제다. 반사적으로 꺼내야 한다.

그런데 "외계어 사전" 같은 변형을 처음 보면? 문자열 비교 문제인 줄 알고 한참 삽질하게 된다. 핵심은 인접한 단어 쌍에서 처음 다른 글자를 찾아 간선으로 만드는 것인데, 이걸 그래프로 모델링할 수 있느냐가 관건이다.

Kahn's vs DFS — 실전에서 뭘 쓸까

두 가지 구현을 먼저 보자.

Kahn's 알고리즘 (BFS 기반)

from collections import deque

def topo_sort_kahn(n, edges):
    indegree = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []

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

    return order if len(order) == n else []  # 빈 리스트면 사이클 존재

DFS 후처리 방식

def topo_sort_dfs(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    state = [0] * n  # 0: 미방문, 1: 진행중, 2: 완료
    order = []

    def dfs(node):
        if state[node] == 1:
            return False  # 사이클 감지
        if state[node] == 2:
            return True
        state[node] = 1
        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        state[node] = 2
        order.append(node)
        return True

    for i in range(n):
        if state[i] == 0 and not dfs(i):
            return []
    return order[::-1]

솔직히 대부분의 상황에서 Kahn's가 낫다. 이유가 몇 가지 있다.

첫째, 사이클 감지가 자연스럽다. 결과 리스트 길이가 N이 아니면 사이클이 있다는 뜻이다. DFS 방식은 상태 관리(진행중 vs 완료)를 직접 해야 한다.

둘째, "사전순 최소"를 요구하는 변형에서 deque를 heapq로 바꾸기만 하면 된다. DFS로는 이게 쉽지 않다.

셋째, Python에서 DFS 재귀는 N이 10만만 넘어도 스택 오버플로 위험이 있다. sys.setrecursionlimit을 올려도 불안하고, 반복문 DFS로 변환하면 코드가 지저분해진다.

"사전순 최소" 변형 — 이거 진짜 자주 나온다

백준 1766번(문제집)이 대표적이다. 단순히 유효한 순서 하나를 구하는 게 아니라, 가능한 모든 순서 중 사전순으로 가장 빠른 걸 출력해야 한다.

import heapq

def topo_sort_lexical(n, edges):
    indegree = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    heap = [i for i in range(n) if indegree[i] == 0]
    heapq.heapify(heap)
    order = []

    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                heapq.heappush(heap, nxt)

    return order

Kahn's 코드에서 deque → heapq로 딱 한 군데 바꿨을 뿐이다. 그런데 이 한 줄 차이를 아느냐 모르느냐가 30분을 좌우한다. 시간 복잡도는 O((V + E) log V)로 약간 올라가지만, 코테 제한 시간 내에서 문제될 일은 거의 없다.

면접에서 나오는 질문들

코테를 넘어 기술 면접에서도 위상 정렬은 단골이다. 자주 받는 질문 네 가지:

"사이클이 있으면?" → Kahn's에선 결과 길이 < N. DFS에선 진행중 상태의 노드를 다시 만남.

"결과가 유일한 조건?" → 매 단계에서 in-degree 0인 노드가 정확히 하나일 때. 큐에 동시에 2개 이상 들어가는 순간이 한 번이라도 있으면 답이 여러 개다.

"시간 복잡도?" → O(V + E). 모든 정점과 간선을 정확히 한 번씩 순회한다.

"실무에서 어디 쓰이냐?" → 이게 의외로 중요하다. npm이 패키지 의존성을 풀 때, CI/CD 파이프라인이 빌드 순서를 잡을 때, 스프레드시트가 셀 계산 순서를 정할 때 — 전부 위상 정렬이다. 이걸 자연스럽게 말할 수 있으면 면접관 인상이 달라진다.

빠지기 쉬운 함정

"위상 정렬 = DAG에서만 가능"이라는 건 다들 안다. 문제는 입력이 DAG라는 보장이 없는 경우다. "순서를 정할 수 없으면 -1을 출력하라" 같은 조건이 문제 끝에 슬쩍 한 줄 붙어있다. 이걸 놓치고 사이클 검증 없이 제출하면 WA를 받는다.

또 하나. 노드 번호가 0부터 시작인지 1부터 시작인지. 사소해 보이지만 indegree 배열 크기를 잘못 잡아서 런타임 에러 맞는 경우가 생각보다 많다. 코테에서 가장 억울한 실수 유형이 이런 off-by-one이다.

위상 정렬 자체의 난이도는 높지 않다. 진짜 실력 차이는 "이게 위상 정렬 문제구나"를 얼마나 빨리 눈치채느냐, 그리고 사전순 최소 같은 변형에서 침착하게 자료구조를 바꿀 수 있느냐에서 갈린다.