언제 쓰나
- 연결된 것들 묶기(연결 요소), 모든 경로/조합 탐색, 백트래킹, 사이클 찾기 → DFS
- 가중치 없는 최단 거리, “최소 몇 번 만에”, 단계별 확산(불, 물, 감염) → BFS
미로에서 “출구까지 최단 거리”는 BFS, “모든 경로의 수”는 DFS다. 최단·최소라는 단어가 보이면 일단 BFS부터 의심한다.
핵심 아이디어
같은 그래프를 어떤 순서로 방문하는지가 다르다. DFS는 스택(재귀), BFS는 큐를 쓴다는 것이 유일한 구조적 차이다.
1
/ \ DFS: 1 → 2 → 4 → 5 → 3 한 갈래를 끝까지
2 3 BFS: 1 → 2 → 3 → 4 → 5 가까운 층부터
/ \
4 5
BFS가 최단 거리인 이유: 거리 0인 노드를 모두 처리한 뒤에야
거리 1을, 그 다음에야 거리 2를 본다 — 처음 도달한 순간이 곧 최단.둘 다 모든 정점과 간선을 한 번씩 보므로 O(V+E)다.
코드 템플릿
그래프는 인접 리스트(defaultdict(list) 또는 리스트의 리스트)로 둔다.
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def dfs(graph, v, visited):
visited[v] = True
for nxt in graph[v]:
if not visited[nxt]:
dfs(graph, nxt, visited)
def bfs(graph, start):
dist = {start: 0}
queue = deque([start])
while queue:
v = queue.popleft()
for nxt in graph[v]:
if nxt not in dist: # 방문 표시 = 거리 기록
dist[nxt] = dist[v] + 1
queue.append(nxt)
return dist코테 최빈출은 2차원 격자 BFS다. 상하좌우 이동을 dx, dy 배열로 처리한다.
def grid_bfs(grid, sr, sc):
n, m = len(grid), len(grid[0])
dist = [[-1] * m for _ in range(n)]
dist[sr][sc] = 0
queue = deque([(sr, sc)])
while queue:
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m \
and grid[nr][nc] == 1 and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist풀이 과정 따라가기
위 그림의 그래프(1—2, 1—3, 2—4, 2—5)를 BFS가 도는 과정이다. 셀은 노드, 강조는 방문 완료를 뜻한다.
같은 그래프를 DFS로 돌면 방문 순서가 1 → 2 → 4 → 5 → 3 — 한 갈래를 끝까지 파고든 뒤 돌아온다.
함정
- 방문 표시는 큐에 넣을 때. 꺼낼 때 표시하면 같은 노드가 큐에 여러 번 들어가 시간·메모리가 터진다.
- 파이썬 재귀 한도. 기본 1,000이라 DFS가 조금만 깊어도
RecursionError.setrecursionlimit을 올리거나 명시적 스택으로 바꾼다. - BFS는 가중치가 전부 같을 때만 최단이다. 간선마다 비용이 다르면 다익스트라(우선순위 큐)로 넘어가야 한다.
- 격자 문제의 행/열 순서.
grid[r][c]에서 r이 세로다. x, y로 이름 지으면 헷갈리기 쉬워 r, c를 권한다.