코딩 테스트 그래프 심화 패턴

그래프 문제는 푸는 기술보다 조건을 보고 알고리즘을 고르는 선택이 합격선을 가릅니다.

알고리즘 선택 기준

그래프 문제에서 시간 초과는 풀이가 틀려서가 아니라 알고리즘을 잘못 골라서 나는 경우가 많습니다. 가중치가 있는지, 음수 간선이 있는지, 한 점에서의 거리인지 모든 쌍의 거리인지가 선택을 가릅니다. 조건을 먼저 읽고 표로 갈라 두면 구현 전에 방향이 정해집니다.

다음은 자주 나오는 조건과 대응 알고리즘입니다. V는 정점 수, E는 간선 수이며, 복잡도는 각 알고리즘의 표준 최악 기준입니다.

방향 비순환 그래프(Directed Acyclic Graph, DAG)는 사이클이 없는 방향 그래프로, 작업 순서나 선후 관계를 표현할 때 쓰입니다. 표의 마지막 두 줄은 거리 계산이 아니라 연결성과 순서를 다루는 문제입니다.

조건을 트리로 그리면 선택이 더 분명해집니다. 아래 그림은 가중치·음수 간선·모든 쌍 여부로 최단 경로 알고리즘을 가르는 흐름입니다.

가중치가 없으면 너비 우선 탐색 한 번으로 끝납니다. 가중치가 있고 음수가 없으면 다익스트라, 음수가 섞이면 벨만-포드로 내려갑니다.

BFS와 다익스트라

무가중치 그래프의 최단 거리는 너비 우선 탐색(Breadth-First Search, BFS)으로 구합니다. 큐로 레벨을 한 칸씩 넓히므로, 어떤 정점에 처음 도달한 시점의 거리가 곧 최단 거리입니다.

가중치가 양수면 큐를 최소 힙으로 바꾼 다익스트라를 씁니다. 가장 가까운 정점부터 꺼내, 그 정점을 거치는 경로가 더 짧으면 거리 값을 줄이는 완화(relax)를 반복합니다.

핵심은 힙에 같은 정점이 여러 번 들어간다는 점입니다. 거리를 줄일 때마다 새 항목을 넣기 때문에, 꺼낸 거리가 이미 기록된 최단 거리보다 크면 오래된 상태이므로 건너뜁니다. 이 한 줄을 빠뜨리면 같은 정점을 중복 처리해 느려집니다.

import heapq
 
def dijkstra(n, adj, src):       # adj[u] = [(v, w), ...]
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:          # 오래된 거리 상태면 버린다
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

정점 A·B·C·D를 0~3으로 두고 간선 A→B(1), A→C(4), B→C(2), B→D(5), C→D(1)을 넣으면 결과는 다음과 같습니다.

dist = [0, 1, 3, 4]

A→C는 직접 가면 4지만 A→B→C가 3이라 더 짧고, 거기서 A→C→D가 4로 확정됩니다.

음수 간선과 전체 쌍 최단 거리

다익스트라는 음수 간선에서 틀립니다. 한 번 꺼내 확정한 거리는 더 줄어들지 않는다고 가정하는데, 음수 간선이 있으면 이 가정이 깨지기 때문입니다.

음수 간선이 섞이면 벨만-포드를 씁니다. 모든 간선을 정점 수보다 하나 적게(V-1번) 완화하고, V번째 완화에서도 거리가 줄면 음수 사이클이 있다는 뜻입니다.

모든 정점 쌍의 거리는 플로이드-워셜로 한 번에 구합니다. 경유지 k를 가장 바깥 루프로 두고 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])를 3중 루프로 갱신합니다. $O(V^3)$이라 정점이 수백 개 이하일 때 적합합니다.

유니온-파인드와 최소 신장 트리

연결성과 사이클은 유니온-파인드(Disjoint Set Union, DSU)로 다룹니다. 원소가 어느 집합에 속하는지 찾고(find) 두 집합을 합치는(union) 두 연산만 제공합니다.

class DSU:
    def __init__(self, n):
        self.p = list(range(n))   # 부모 포인터
        self.r = [0] * n          # 랭크(트리 높이 상한)
 
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])   # 경로 압축
        return self.p[x]
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False          # 이미 같은 집합 → 사이클
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra       # 랭크 큰 쪽을 루트로
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True

find는 부모를 따라 올라가 루트를 찾고, 거친 노드를 루트에 바로 붙이는 경로 압축을 합니다. union은 높이 상한인 랭크가 큰 쪽을 루트로 삼아 트리가 깊어지지 않게 막습니다. 두 최적화를 합치면 한 연산이 거의 상수 시간(역 아커만 함수 $O(\alpha(n))$)에 끝납니다.

union이 false를 돌려주면 두 끝점이 이미 같은 집합이라는 뜻이고, 그 간선은 사이클을 만듭니다. 이 성질을 그대로 쓰면 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 크루스칼이 됩니다.

def kruskal(n, edges):           # edges = [(w, a, b), ...]
    dsu = DSU(n)
    total = 0
    for w, a, b in sorted(edges):
        if dsu.union(a, b):      # 사이클을 안 만들 때만 채택
            total += w
    return total

간선을 가중치 오름차순으로 정렬하고, 사이클을 만들지 않는 간선만 차례로 채택합니다. 정점 5개에 다음 간선이 주어졌다고 하겠습니다.

(가중치, 양끝) = (1, 0-1) (2, 0-2) (3, 1-2) (4, 2-3) (5, 3-4) (6, 2-4)

가중치 1·2·4·5 간선이 채택되고, 3과 6은 양끝이 이미 같은 집합이라 사이클을 만들어 빠집니다. 따라서 신장 트리의 가중치 합은 12입니다.

위상 정렬과 사이클 감지

작업 순서나 선후 관계는 위상 정렬로 풉니다. 진입 차수(들어오는 간선 수)가 0인 정점부터 처리하는 칸(Kahn) 방식이 구현이 단순합니다.

진입 차수가 0인 정점을 큐에 넣고 하나씩 꺼내 결과에 붙입니다. 꺼낸 정점에서 나가는 간선을 제거해 인접 정점의 진입 차수를 줄이고, 0이 되면 큐에 넣습니다.

from collections import deque
 
def topo_sort(n, adj):           # adj[u] = [v, ...]
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # None이면 사이클

정렬 결과의 길이가 정점 수보다 작으면 큐가 중간에 비었다는 뜻이고, 남은 정점들은 서로 물고 도는 사이클입니다. 위상 정렬 한 번으로 순서 결정과 사이클 감지를 함께 처리합니다.

자주 하는 실수와 기출 점검

구현이 맞아도 다음 지점에서 자주 틀립니다.

• 무가중치 그래프에 다익스트라를 써서 불필요한 로그 비용을 더합니다.
• 다익스트라에서 오래된 거리 건너뛰기를 빠뜨려 중복 처리로 느려집니다.
• 1-indexed와 0-indexed 변환을 놓쳐 인덱스 오류가 납니다.
• 재귀 DFS를 쓰다 깊은 그래프에서 스택 오버플로가 납니다.

연습은 유형별로 한 문제씩 잡는 편이 효율적입니다. 아래는 백준 온라인 저지(BOJ)와 프로그래머스의 대표 문제이며, 난이도는 2026-06 기준 solved.ac 티어와 프로그래머스 레벨입니다.

문제마다 핵심 한 줄이 다르므로, 풀고 난 뒤 어느 조건이 알고리즘을 결정했는지 메모해 두면 다음 문제에서 분류가 빨라집니다.

정리

그래프 문제는 조건을 읽고 알고리즘을 고르는 단계에서 대부분 갈립니다. 가중치와 음수 간선 유무로 BFS·다익스트라·벨만-포드를 가르고, 모든 쌍이면 플로이드-워셜을 씁니다. 연결성과 사이클은 유니온-파인드, 선후 관계는 위상 정렬이 표준 도구입니다. 다익스트라의 오래된 거리 건너뛰기나 위상 정렬의 사이클 감지처럼, 템플릿마다 빠뜨리기 쉬운 한 줄을 기억하면 실수를 줄일 수 있습니다.