그래프 탐색 안내서 · 6/6

실무 활용

그래프 탐색은 코딩 테스트만의 기술이 아닙니다. 빌드 도구, 패키지 관리자, 가비지 컬렉터, 웹 크롤러, 그림 편집기의 채우기 도구가 모두 이 장에서 본 BFS, DFS, 위상 정렬 위에서 동작합니다. 이 장에서는 실제 시스템의 예와 표준 라이브러리, 그리고 자주 하는 실수를 정리합니다.

실제 시스템 속 그래프 탐색

빌드 시스템과 작업 실행기: Make, Bazel, Gradle, CI 파이프라인은 작업 사이의 의존 관계를 DAG로 만들고 위상 순서대로 실행합니다. 진입 차수가 0인 작업들은 동시에 실행할 수 있어 병렬 빌드의 근거가 됩니다.
패키지 관리자: npm, pip, Cargo 같은 도구는 의존성 그래프를 따라가며 설치 순서를 정하고, 순환 의존을 찾아 알려 줍니다.
가비지 컬렉터: 표시-청소(mark-and-sweep) 방식은 루트(전역 변수, 스택)에서 참조를 따라 탐색해 도달 가능한 객체에 표시하고, 표시되지 않은 객체를 회수합니다.
웹 크롤러: 시작 페이지에서 링크를 따라 BFS로 넓혀 가며, 깊이 제한과 방문 집합으로 같은 페이지를 다시 받지 않습니다.
그림 편집기의 채우기: 클릭한 픽셀과 같은 색으로 이어진 영역을 격자 BFS나 DFS로 찾아 칠합니다(flood fill).
스프레드시트: 셀 수식의 참조 관계를 위상 정렬해 다시 계산할 순서를 정하고, 순환 참조를 오류로 알립니다.
교착 상태 탐지: 데이터베이스는 "누가 누구의 잠금을 기다리는가"를 방향 그래프로 만들고, 사이클이 생기면 교착 상태로 판단합니다.

표준 라이브러리와 도구

Python 3.9부터는 표준 라이브러리 graphlib에 위상 정렬이 들어 있습니다. 사전의 값은 "먼저 끝나야 하는 것"(선행 노드)입니다.

from graphlib import TopologicalSorter, CycleError

deps = {"app": {"ui", "net"}, "ui": {"core"}, "net": {"core"}}
print(list(TopologicalSorter(deps).static_order()))
# 예: ['core', 'ui', 'net', 'app'] (같은 단계 안의 순서는 정해져 있지 않음)

try:
    list(TopologicalSorter({"a": {"b"}, "b": {"a"}}).static_order())
except CycleError as error:
    print("순환 의존:", error.args[1])

TopologicalSorter는 prepare(), get_ready(), done()으로 준비된 작업을 여러 작업자에게 나눠 주는 병렬 실행도 지원합니다. 그래프를 본격적으로 다룬다면 NetworkX가 BFS, DFS, 연결 요소, 위상 정렬을 모두 제공합니다.

import networkx as nx

grid = nx.grid_2d_graph(3, 3)                       # 3 x 3 격자 그래프
print(nx.shortest_path_length(grid, (0, 0), (2, 2)))  # 4, 가중치가 없으면 BFS
print(nx.number_connected_components(nx.Graph([(0, 1), (2, 3)])))  # 2
print(list(nx.topological_sort(nx.DiGraph([("core", "ui"), ("ui", "app")]))))

가비지 컬렉터의 표시 단계는 결국 반복형 DFS입니다.

def mark(roots, refs):
    live, stack = set(), list(roots)
    while stack:
        obj = stack.pop()
        if obj in live:
            continue
        live.add(obj)
        stack.extend(refs.get(obj, []))
    return live

refs = {"main": ["a"], "a": ["b"], "b": ["a"], "c": ["d"]}
print(mark(["main"], refs))  # {'main', 'a', 'b'}: c와 d는 회수 대상

a와 b가 서로를 참조하는 순환이 있어도 방문 집합 덕분에 끝나고, 루트에서 닿지 않는 c와 d는 참조 횟수와 상관없이 회수됩니다.

자주 하는 실수

방문 표시 시점: BFS에서 꺼낼 때 표시하면 같은 정점이 큐에 여러 번 들어가 메모리와 시간이 크게 늘어납니다. 넣을 때 표시하세요.
리스트를 큐로 쓰기: list.pop(0)과 JavaScript의 shift()는 O(n)입니다.
재귀 깊이: 정점이 수만 개인 일직선 그래프에서 재귀 DFS는 스택이 넘칩니다.
방향 그래프의 사이클 판단: 방향 그래프에서는 "이미 방문한 정점"을 만났다고 사이클이 아닙니다. 탐색 중(GRAY)인 정점을 만나야 사이클입니다. 무방향 그래프에서는 바로 직전 부모로 돌아가는 간선을 사이클로 착각하지 않아야 합니다.
끝이 없는 암시적 그래프: 크롤러나 상태 공간 탐색처럼 정점이 무한할 수 있으면 깊이나 개수 제한을 반드시 둡니다.
도달하지 못한 정점: 거리가 -1인 정점을 그대로 계산에 쓰지 않도록 확인합니다.

정리

의존 관계가 있는 곳에는 위상 정렬이, 도달 가능성을 묻는 곳에는 BFS나 DFS가 있습니다. 실무에서는 graphlib이나 NetworkX 같은 검증된 구현을 먼저 쓰고, 직접 구현할 때는 방문 표시 시점, 큐 자료 구조, 재귀 깊이, 사이클 판단 기준을 확인하세요.

더 읽을거리

이 장에 대해 질문이 있나요?