DFS/BFS — 깊이 우선 vs 너비 우선

이 토픽을 마치면

DFS와 BFS가 그래프를 탐색하는 방식의 차이를 이해하고, 문제 유형에 따라 어떤 걸 써야 하는지 판단할 수 있게 됩니다.

미로를 탈출하는 두 가지 전략

미로에 들어갔습니다. 갈림길이 나옵니다. 두 가지 전략이 있습니다.

전략 A: 한 방향을 선택하고 끝까지 갑니다. 막히면 마지막 갈림길로 돌아와서 다른 길을 시도합니다. 한 우물을 깊이 파는 방식입니다.

전략 B: 갈림길에서 모든 방향을 한 발짝씩 전진합니다. 그 다음 갈림길에서도 모든 방향을 한 발짝씩. 동심원처럼 퍼져나가는 방식입니다.

전략 A가 DFS(Depth-First Search, 깊이 우선 탐색), 전략 B가 **BFS(Breadth-First Search, 너비 우선 탐색)**입니다.

DFS — 한 길을 끝까지

text

A
   / \
  B   C
 / \   \
D   E   F

A에서 시작해서 DFS로 탐색하면: A → B → D → (막힘, 돌아감) → E → (돌아감) → C → F

한 갈래를 선택하면 끝까지 내려갑니다. 더 갈 곳이 없으면 되돌아와서(backtrack) 다른 갈래를 탐색합니다.

구현은 스택(Stack) 또는 **재귀(Recursion)**를 씁니다:

python

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

재귀 호출 자체가 스택처럼 동작합니다. 함수가 함수를 호출하면서 깊이 들어가고, return하면서 돌아옵니다.

BFS — 가까운 것부터 전부

같은 트리를 BFS로 탐색하면: A → B → C → D → E → F

A에서 한 칸 떨어진 B, C를 먼저 방문합니다. 그 다음 두 칸 떨어진 D, E, F를 방문합니다. 거리가 가까운 순서대로 탐색합니다.

구현은 **큐(Queue)**를 씁니다:

python

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

큐에 넣은 순서대로 처리하니까 가까운 노드가 먼저 나옵니다.

핵심 차이: 스택 vs 큐

DFS와 BFS의 코드는 거의 동일합니다. 차이는 어떤 자료구조로 다음 노드를 관리하느냐뿐입니다.

text

DFS: 스택 (또는 재귀) → 마지막에 넣은 것을 먼저 꺼냄 → 깊이 방향
BFS: 큐              → 먼저 넣은 것을 먼저 꺼냄     → 너비 방향

자료구조 하나 바꾸면 탐색 순서가 완전히 달라집니다.

언제 뭘 쓰나

DFS가 적합한 경우:

경로가 존재하는지 확인 (있다/없다)
모든 경우의 수를 탐색해야 할 때 (백트래킹)
미로에서 출구 하나만 찾으면 될 때
메모리를 적게 쓰고 싶을 때 (현재 경로만 저장)

BFS가 적합한 경우:

최단 경로를 찾아야 할 때
가까운 것부터 탐색해야 할 때
SNS에서 "친구의 친구" 추천
네트워크에서 가장 가까운 서버 찾기

가장 중요한 구분: 최단 거리가 필요하면 BFS, 존재 여부만 확인하면 DFS.

BFS는 가까운 노드부터 방문하니까 처음 도착한 경로가 곧 최단 경로입니다. DFS는 깊이 방향으로 파고들기 때문에 최단 경로를 보장하지 못합니다.

시간 복잡도

둘 다 **O(V + E)**입니다. V는 노드 수, E는 간선 수. 모든 노드를 한 번씩, 모든 간선을 한 번씩 확인합니다. 탐색 순서만 다를 뿐 전체 작업량은 같습니다.

공간 복잡도는 다릅니다. DFS는 현재 탐색 경로의 깊이만큼 스택을 씁니다. BFS는 같은 레벨의 노드를 전부 큐에 넣으니까, 너비가 넓은 그래프에서 메모리를 더 씁니다.

핵심

DFS는 한 방향을 끝까지 탐색하고 막히면 되돌아갑니다. 스택/재귀를 씁니다. BFS는 가까운 것부터 전부 탐색합니다. 큐를 씁니다. 최단 경로가 필요하면 BFS, 존재 여부만 확인하면 DFS가 적합합니다.