복잡도

그래프 탐색의 비용은 정점 수 V와 간선 수 E, 그리고 그래프를 어떻게 저장했는지에 따라 정해집니다. 이 장에서는 BFS, DFS, 위상 정렬의 시간과 공간을 분석하고, 표현 방식과 다른 알고리즘과의 차이를 표로 비교합니다.

왜 O(V + E)인가

인접 리스트 위에서 BFS나 DFS를 돌리면 다음 두 가지가 성립합니다.

• 방문 표시 덕분에 각 정점은 큐(또는 스택)에 한 번만 들어가고 한 번만 꺼내집니다. 여기서 O(V)가 나옵니다.
• 정점을 꺼낼 때 그 정점의 이웃 목록을 한 번 훑습니다. 모든 정점의 이웃 목록 길이를 더하면 방향 그래프는 E, 무방향 그래프는 2E입니다. 여기서 O(E)가 나옵니다.

그래서 전체 시간은 O(V + E)입니다. BFS와 DFS는 최선, 평균, 최악이 따로 없고 도달 가능한 부분 전체를 보면 항상 이 비용이 듭니다. 목표 정점을 찾자마자 멈추는 경우에만 더 빨리 끝날 수 있습니다.

인접 행렬을 쓰면 한 정점의 이웃을 찾기 위해 행 전체 V칸을 봐야 하므로 시간이 O(V^2)가 됩니다. 간선이 적은 그래프에서는 큰 차이입니다.

from collections import deque

def bfs_matrix(matrix, start):
    n = len(matrix)
    dist = [-1] * n
    dist[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in range(n):               # 이웃이 아니어도 n칸을 모두 본다
            if matrix[u][v] and dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist                          # 전체 O(V^2)

공간

• 방문 표시, 거리, 부모 배열: O(V)
• BFS 큐: 최악의 경우 한 겹 전체가 들어가므로 O(V)
• DFS 스택 또는 재귀 깊이: 최악의 경우 일직선 그래프에서 O(V)
• 그래프 자체: 인접 리스트 O(V + E), 인접 행렬 O(V^2)

표현 방식 비교

간선이 정점 수의 제곱에 가까운 조밀한 그래프(예: 정점 1000개, 간선 수십만 개)에서는 행렬도 괜찮은 선택이지만, 실무와 코딩 테스트의 대부분은 희소 그래프라 인접 리스트가 기본입니다. 이웃 여부를 자주 묻는다면 리스트 대신 집합(set)을 이웃 목록으로 써서 평균 O(1) 확인을 얻을 수 있습니다.

격자 그래프

R x C 격자는 정점이 RC개, 정점마다 이웃이 최대 4개이므로 간선도 O(RC)입니다. 격자 BFS는 O(RC) 시간과 공간이 듭니다. 1000 x 1000 격자면 정점 백만 개이므로 Python에서는 리스트 대신 1차원 배열 인덱스(r * C + c)를 쓰는 등 상수 비용을 줄이는 것이 체감됩니다.

다른 알고리즘과의 비교

가중치가 모두 같으면 다익스트라 대신 BFS를 쓰는 것이 더 빠르고 간단합니다.

상수 비용을 키우는 실수

리스트를 큐로 쓰면 pop(0)이 매번 남은 원소를 앞으로 당겨서 BFS가 O(V^2)로 느려집니다.

from collections import deque
import timeit

def drain_list(n):
    items = list(range(n))
    while items:
        items.pop(0)          # 매번 O(n)

def drain_deque(n):
    items = deque(range(n))
    while items:
        items.popleft()       # 매번 O(1)

n = 100_000
print(timeit.timeit(lambda: drain_list(n), number=1))
print(timeit.timeit(lambda: drain_deque(n), number=1))

재귀 DFS는 Python의 재귀 한도(기본 약 1000)를 넘으면 RecursionError가 납니다. 한도를 올릴 수 있지만 C 스택이 넘치면 프로세스가 죽을 수 있으므로, 깊은 그래프는 반복형으로 바꾸는 것이 안전합니다.

import sys

def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)

print(sys.getrecursionlimit())   # 보통 1000
try:
    depth(5000)
except RecursionError:
    print("재귀가 너무 깊습니다. 반복형 DFS를 쓰세요.")

정리

인접 리스트 위의 BFS, DFS, 위상 정렬은 모두 O(V + E) 시간에 O(V) 추가 공간을 씁니다. 인접 행렬은 이웃 확인이 빠른 대신 탐색이 O(V^2)가 됩니다. 실제 속도는 deque를 쓰는지, 재귀 깊이를 피했는지 같은 구현 선택에도 크게 좌우됩니다.