DFS와 BFS (Depth First Search, Breadth First Search)

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프의 모든 정점을 빠짐없이 한 번씩 방문하는 두 가지 방법이다. 방문할 곳을 스택에 쌓느냐 큐에 담느냐, 차이는 이것 하나뿐인데 탐색 순서와 쓰임새가 완전히 달라진다.

코딩테스트에서 가장 출제 빈도가 높은 주제다. 미로 최단 거리, 섬 개수 세기, 네트워크 연결 판정, 바이러스 확산 같은 문제가 전부 이 둘 중 하나로 풀린다. "최단"이라는 단어가 보이면 BFS라는 감각만 잡아도 절반은 간다.

두 탐색의 차이

DFS는 한 길로 갈 수 있는 데까지 파고들었다가 막히면 돌아 나와 다른 길을 본다. BFS는 가까운 곳부터 한 겹씩 넓혀 나간다.

스택과 큐, 차이는 여기서 갈린다

두 알고리즘의 코드는 사실상 같다. "다음에 방문할 후보"를 담아두는 자료구조만 다르다.

BFS가 최단 거리를 주는 이유

BFS는 시작점에서 거리 1인 정점을 전부, 그다음 거리 2인 정점을 전부 방문한다. 그래서 어떤 정점에 처음 도착하는 순간이 곧 최단 경로로 도착한 순간이다. 나중에 다른 경로로 같은 정점에 닿더라도 그 경로가 더 짧을 수는 없다.

단, 이 성질은 모든 간선의 가중치가 같을 때만 성립한다. 간선마다 비용이 다르면 BFS는 최단 거리를 보장하지 못하고 다익스트라를 써야 한다. DFS는 어떤 경우에도 최단 거리를 주지 않는다. 운 좋게 맞을 수는 있어도 보장이 없다.

시간 복잡도

구분	인접 리스트	인접 행렬
시간	O(V + E)	O(V²)
공간	O(V + E)	O(V²)

DFS와 BFS의 복잡도는 같다. 모든 정점을 한 번씩, 모든 간선을 한 번씩(무방향이면 두 번) 훑기 때문이다. 정점 수에 비해 간선이 적은 희소 그래프에서는 인접 리스트가 압도적으로 유리하다. 코딩테스트에서는 거의 항상 인접 리스트를 쓴다.

추가 공간은 방문 체크 배열 O(V)에, DFS는 재귀 스택 O(V), BFS는 큐 O(V)가 붙는다.

구현 코드 예시

from collections import deque


def dfs_recursive(graph, v, visited, order):
    visited[v] = True
    order.append(v)
    for nxt in graph[v]:
        if not visited[nxt]:
            dfs_recursive(graph, nxt, visited, order)


def dfs_stack(graph, start, n):
    """재귀 없이 스택으로 구현한 DFS."""
    visited = [False] * (n + 1)
    stack = [start]
    order = []

    while stack:
        v = stack.pop()
        if visited[v]:            # 스택에는 중복이 들어올 수 있어 꺼낼 때 확인
            continue
        visited[v] = True
        order.append(v)
        for nxt in reversed(graph[v]):   # 작은 번호부터 방문하려면 뒤집어 넣는다
            if not visited[nxt]:
                stack.append(nxt)
    return order


def bfs(graph, start, n):
    visited = [False] * (n + 1)
    q = deque([start])
    visited[start] = True         # 큐에 넣는 순간 방문 표시
    order = []

    while q:
        v = q.popleft()
        order.append(v)
        for nxt in graph[v]:
            if not visited[nxt]:
                visited[nxt] = True
                q.append(nxt)
    return order

최단 거리가 필요하면 방문 배열 대신 거리 배열을 쓴다. 코드가 거의 바뀌지 않는다.

def bfs_dist(graph, start, n):
    dist = [-1] * (n + 1)         # -1은 아직 도달하지 못했다는 뜻
    dist[start] = 0
    q = deque([start])

    while q:
        v = q.popleft()
        for nxt in graph[v]:
            if dist[nxt] == -1:
                dist[nxt] = dist[v] + 1
                q.append(nxt)
    return dist


# 2차원 격자(미로) 문제의 관용구
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs_grid(board, sr, sc):
    h, w = len(board), len(board[0])
    dist = [[-1] * w for _ in range(h)]
    dist[sr][sc] = 0
    q = deque([(sr, sc)])

    while q:
        r, c = q.popleft()
        for d in range(4):
            nr, nc = r + dx[d], c + dy[d]
            if 0 <= nr < h and 0 <= nc < w and dist[nr][nc] == -1 and board[nr][nc] == 1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist