[CS300 #074] BFS 와 DFS — 그래프를 빠짐없이 한 번씩 도는 두 방법

컴퓨터공학 300 주제 시리즈의 074번째 글이다. 전체 지도는 여기.

한 줄 요약

너비 우선 탐색(BFS)은 큐로 가까운 정점부터 층층이 넓혀 가고, 깊이 우선 탐색(DFS)은 스택(또는 재귀)으로 한 길을 끝까지 판 뒤 되돌아온다. 둘 다 정점 V 개, 간선 E 개 그래프를 Θ(V + E) 에 한 번씩 방문한다. 가중치 없는 최단 거리는 BFS, 구조 분석(사이클, 위상 정렬, 연결 요소)은 DFS 가 주무기다.

왜 필요한가

그래프는 어디에나 있다. 웹 페이지와 링크, 패키지와 의존성, 서비스와 호출 관계, 쿠버네티스 오브젝트와 소유 관계. 이런 구조에서 “여기서 저기까지 갈 수 있나”, “가장 가까운 경로는”, “순환이 있나” 를 묻는 순간 탐색이 필요하다.

BFS 와 DFS 는 이후 나올 그래프 알고리즘(다익스트라, 위상 정렬, 최소 신장 트리)의 바탕이다. 둘의 차이는 “다음에 방문할 후보를 담는 자료구조” 하나뿐이다. 그런데 그 하나가 결과의 성질을 완전히 바꾼다.

핵심 개념

그래프 표현

표현	공간	이웃 나열	간선 (u,v) 존재 확인
인접 리스트	Θ(V + E)	이웃 수만큼	이웃 수만큼
인접 행렬	Θ(V²)	Θ(V)	Θ(1)

대부분의 실제 그래프는 희소(E 가 V² 보다 훨씬 작음)하므로 인접 리스트를 쓴다. 아래 복잡도도 인접 리스트 기준이다.

BFS

     A               층 0: A
    / \              층 1: B C
   B   C             층 2: D E F
  / \   \
 D   E → F

시작 정점을 큐에 넣고 방문 표시한다.
큐에서 하나 꺼내고, 방문하지 않은 이웃을 모두 표시하고 큐에 넣는다.
큐가 빌 때까지 반복한다.

큐는 먼저 들어온 것이 먼저 나간다. 그래서 거리 0 인 정점, 거리 1 인 정점들, 거리 2 인 정점들 순으로 처리된다. 이 성질 때문에 가중치가 없는 그래프에서 BFS 가 처음 도달한 거리가 곧 최단 거리 다.

방문 표시는 큐에서 꺼낼 때가 아니라 넣을 때 한다. 꺼낼 때 표시하면 같은 정점이 큐에 여러 번 들어가 메모리와 시간이 낭비된다.

DFS

DFS 는 갈 수 있는 데까지 한 방향으로 깊이 들어간다. 막히면 마지막 갈림길로 되돌아가(backtrack) 다른 길을 간다. 재귀 호출의 콜 스택이 곧 탐색 스택이다.

DFS 는 각 정점에 “들어간 시각” 과 “나온 시각” 을 남기는데, 이 시각 정보가 강력하다.

방향 그래프에서 “현재 재귀 스택 위에 있는 정점” 으로 가는 간선(back edge)이 있으면 사이클이 있다.
나온 시각의 역순이 위상 정렬 순서다(뒤에서 다룬다).
강한 연결 요소, 단절점, 다리를 찾는 Tarjan 의 알고리즘이 모두 DFS 위에 있다. Tarjan 이 1972년 논문에서 정리했다.

재귀 DFS 의 한계

재귀 깊이가 정점 수만큼 깊어질 수 있다. CPython 의 기본 재귀 한도는 1000 수준이라(sys.getrecursionlimit()) 긴 사슬 그래프에서 RecursionError 가 난다. 운영 코드에서는 명시적 스택을 쓰는 반복 버전이 안전하다.

비교

	BFS	DFS
자료구조	큐	스택 / 재귀
시간	Θ(V + E)	Θ(V + E)
가중치 없는 최단 거리	보장	보장 안 함
메모리	한 층의 폭만큼 (넓은 그래프에서 큼)	경로 깊이만큼 (깊은 그래프에서 큼)
잘 맞는 문제	최단 거리, 가까운 것부터 찾기, 층별 처리	사이클 탐지, 위상 정렬, 연결 요소, 백트래킹

왜 Θ(V + E) 인가

방문 표시 덕분에 각 정점은 큐(스택)에 최대 한 번 들어가고 한 번 나온다. Θ(V). 각 정점을 꺼낼 때 그 인접 리스트를 한 번 훑으므로, 모든 인접 리스트 길이의 합 Θ(E) 만큼 이웃을 본다. 합쳐서 Θ(V + E).

직접 해 보기

같은 그래프에서 BFS, 재귀 DFS, 반복 DFS 를 돌리고, 연결 요소를 세고, 미로의 최단 거리를 구한다. python3 로 실행해 확인했다.

from collections import deque

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [],
         "E": ["F"], "F": [], "G": ["H"], "H": []}   # G, H 는 A 에서 닿지 않음

def bfs(start):
    dist, order, q = {start: 0}, [], deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in dist:            # 큐에 넣을 때 방문 표시
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist

def dfs(start):
    order, seen = [], set()
    def go(u):
        seen.add(u); order.append(u)
        for v in graph[u]:
            if v not in seen:
                go(v)
    go(start)
    return order

def dfs_iter(start):
    order, seen, stack = [], set(), [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u); order.append(u)
        for v in reversed(graph[u]):     # 재귀 버전과 같은 순서를 내려고 뒤집어 넣는다
            if v not in seen:
                stack.append(v)
    return order

print("BFS 순서:", bfs("A")[0])
print("BFS 거리:", bfs("A")[1])
print("DFS 재귀:", dfs("A"))
print("DFS 반복:", dfs_iter("A"))

# 연결 요소 세기 (무향으로 보고)
und = {u: set() for u in graph}
for u, vs in graph.items():
    for v in vs:
        und[u].add(v); und[v].add(u)
seen, comps = set(), []
for s in und:
    if s in seen:
        continue
    comp, stack = [], [s]
    seen.add(s)
    while stack:
        u = stack.pop(); comp.append(u)
        for v in und[u]:
            if v not in seen:
                seen.add(v); stack.append(v)
    comps.append(sorted(comp))
print("연결 요소:", comps)

# 격자 미로 최단 거리 (BFS)
maze = ["S.#.",
        "..#.",
        "...E"]
R, C = len(maze), len(maze[0])
start, goal = (0, 0), (2, 3)
d, q = {start: 0}, deque([start])
while q:
    r, c = q.popleft()
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and maze[nr][nc] != "#" and (nr, nc) not in d:
            d[(nr, nc)] = d[(r, c)] + 1; q.append((nr, nc))
print("미로 최단 거리:", d.get(goal))

출력:

BFS 순서: ['A', 'B', 'C', 'D', 'E', 'F']
BFS 거리: {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}
DFS 재귀: ['A', 'B', 'D', 'E', 'F', 'C']
DFS 반복: ['A', 'B', 'D', 'E', 'F', 'C']
연결 요소: [['A', 'B', 'C', 'D', 'E', 'F'], ['G', 'H']]
미로 최단 거리: 5

BFS 는 층 순서(A / B C / D E F), DFS 는 A→B→D 로 끝까지 판 뒤 돌아와 E→F, 마지막에 C 를 방문했다. F 는 C 에서도 E 에서도 갈 수 있지만 두 탐색 모두 한 번만 방문했다. 반복 DFS 에서 이웃을 뒤집어 넣은 것은 스택이 마지막에 넣은 것을 먼저 꺼내기 때문이다.

현업에서는

쿠버네티스 가비지 컬렉션. 오브젝트는 ownerReferences 로 소유자를 가리킨다. Deployment → ReplicaSet → Pod 로 이어지는 소유 그래프에서, 소유자를 지우면 종속 오브젝트를 따라가며 지우는 연쇄 삭제(cascading deletion)가 일어난다. 공식 문서는 foreground 와 background 두 방식을 설명한다. 그래프를 따라 내려가 종속 오브젝트를 모두 찾는다는 점에서 탐색 문제다.
의존성 분석. “이 라이브러리를 올리면 영향받는 서비스는?” 은 역방향 의존 그래프에서 BFS/DFS 로 도달 가능한 정점을 모으는 문제다.
웹 크롤러와 링크 검사. 시작 페이지에서 BFS 로 링크를 따라가면 가까운 페이지부터 확인할 수 있다. 방문 집합이 없으면 서로 링크한 페이지 사이에서 영원히 돈다.
네트워크. 홉 수가 가장 적은 경로, 브로드캐스트가 몇 단계에 퍼지는지 같은 질문은 BFS 층 번호로 답한다.

확인 문제

BFS 에서 방문 표시를 큐에서 꺼낼 때 하면 무엇이 문제인가?
가중치가 있는 그래프에서 BFS 가 최단 거리를 보장하지 않는 이유는?
정점 10만 개가 일렬로 이어진 그래프에서 Python 재귀 DFS 를 돌리면 어떻게 되는가?
인접 행렬로 표현된 그래프에서 BFS 의 시간 복잡도는?

풀이

같은 정점이 아직 꺼내지기 전에 여러 이웃에 의해 중복으로 큐에 들어간다. 결과는 맞을 수 있지만 큐 크기와 시간이 커진다(최악 Θ(E) 개가 들어감).
BFS 는 간선 개수가 적은 경로를 먼저 찾는다. 간선 수가 적어도 가중치 합이 더 클 수 있다. 가중치가 있으면 다익스트라를 쓴다.
재귀 깊이가 기본 한도를 넘어 RecursionError 가 난다. 명시적 스택을 쓴 반복 버전으로 바꾼다.
정점마다 행 전체(V 칸)를 훑어야 하므로 Θ(V²).

더 읽을거리 (References)

Robert Tarjan, “Depth-First Search and Linear Graph Algorithms”, SIAM Journal on Computing 1(2), 1972.
Kubernetes 공식 문서, Garbage Collection
NIST Dictionary of Algorithms and Data Structures, breadth-first search, depth-first search
Python 공식 문서, collections.deque