DFS & BFS란?
DFS (Depth-First Search): 가능한 깊게 들어가서 더 이상 갈 곳이 없으면 한 단계씩 되돌아오는 방식.
비유: 미로에서 한 갈래로 쭉 들어가서 막다른 길이면 뒤로 와서 다른 갈래로 간다.
BFS (Breadth-First Search): 현재 레벨(거리)에 있는 모든 노드를 먼저 방문하고, 다음 레벨로 넘어가는 방식.
비유: 물결이 퍼지듯이 가까운 곳부터 하나씩 넓게 퍼져 나간다.
왜 DFS & BFS 를 배울까요?
-정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에,
모든 경우의 수를 전부 탐색해야 하는 경우도 있다.
- 대표적인 예시가 알파고이다.
대국에서 발생하는 모든 수를 계산하고 예측해서 최적의 수를 계산해내기 위해
모든 수를 전부 탐색해야 한다. - DFS 와 BFS 는 그 탐색하는 순서에서 차이가 있다.
DFS 는 끝까지 파고드는 것이고,
BFS 는 갈라진 모든 경우의 수를 탐색해보고 오는 것이 차이점이다.
직관적 예시(작은 그래프)
그래프(인접리스트):
graph = {
'A': ['B','C'],
'B': ['A','D','E'],
'C': ['A','F'],
'D': ['B'],
'E': ['B','F'],
'F': ['C','E']
}
BFS (start = A) 방문 순서(가능한 한): A → B → C → D → E → F
→ A(거리0), B,C(거리1), D,E,F(거리2) 순서
DFS (start = A, 재귀 방식, 인접 순서 사용) 방문 순서(가능한 한): A → B → D → E → F → C
→ A → B → (B의 첫 자식 D) → D 막다르면 돌아와서 E → E에서 F → 그리고 마지막에 C
Python 예제 (직관적이고 안전한 패턴)
DFS — 재귀 버전
def dfs_recursive(graph, node, visited=None, order=None):
if visited is None:
visited = set()
if order is None:
order = []
visited.add(node) # 들어오자마자 방문 표시
order.append(node)
for neigh in graph.get(node, []):
if neigh not in visited:
dfs_recursive(graph, neigh, visited, order)
return order
# 사용:
# dfs_recursive(graph, 'A') => ['A','B','D','E','F','C']
DFS — 반복(스택) 버전
def dfs_iterative(graph, start):
visited = set([start])
stack = [start]
order = []
while stack:
node = stack.pop()
order.append(node)
# 재귀와 같은 순서를 원하면 이웃을 역순으로 스택에 넣음
for neigh in reversed(graph.get(node, [])):
if neigh not in visited:
visited.add(neigh)
stack.append(neigh)
return order
BFS — 큐(최단 간선수 보장)
from collections import deque
def bfs(graph, start):
visited = set([start])
q = deque([start])
order = []
while q:
node = q.popleft()
order.append(node)
for neigh in graph.get(node, []):
if neigh not in visited:
visited.add(neigh)
q.append(neigh)
return order
# bfs(graph, 'A') => ['A','B','C','D','E','F']
BFS로 최단 경로(비가중치 그래프) 구하기
from collections import deque
def bfs_shortest_path(graph, start, goal):
visited = set([start])
parent = {start: None}
q = deque([start])
while q:
node = q.popleft()
if node == goal:
# 경로 재구성
path = []
while node is not None:
path.append(node)
node = parent[node]
return list(reversed(path))
for neigh in graph.get(node, []):
if neigh not in visited:
visited.add(neigh)
parent[neigh] = node
q.append(neigh)
return None # 경로 없음
# bfs_shortest_path(graph, 'A', 'F') => ['A','C','F'] (인접 순서에 따라 달라질 수 있음)
주의: visited는 노드를 큐(또는 스택)에 넣을 때 표시하는 게 중복 enqueue/push를 막아 효율적입니다.
시간/공간 복잡도
시간: O(V + E) (V = 정점 수, E = 간선 수) — 인접 리스트 기준
공간: 방문 체크, 큐/스택, 재귀 호출 스택 등으로 O(V)
(인접 행렬이면 시간/공간 조건이 달라짐: 행렬 접근은 O(1)지만 전체 탐색에 O(V^2))
언제 DFS를 쓰고 언제 BFS를 써야 할까?
- BFS
무가중 그래프에서 최단 경로(간선 수 기준) 를 구할 때.
“가장 가까운” 것을 찾는 문제 (예: 탈출까지의 최소 단계).
- DFS
그래프의 모든 경로를 탐색하거나 (경로 존재 여부, 경로 수 카운트)
사이클 검출, Topological sort(위상 정렬), 연결 요소 개수 구할 때.
메모리 제약이 있거나 재귀적 구조(트리 등)의 순회에 자연적.
자주 하는 실수 & 디버깅 팁
- visited 체크를 안 해서 무한 루프
- 무방향 그래프에서 A→B, B→A가 반대 방향으로 가면서 계속 반복됨. → 꼭 방문 체크!
- visited 위치 실수
- 큐/스택에 넣을 때 visited.add(...) 해야 중복으로 여러 번 enqueue/push 안 함.
(팝 후에 visited 표시하면 여러 번 들어갈 수 있음)
- 재귀 깊이 초과(RecursionError)
- 큰 그래프에서 재귀 DFS는 RecursionError 발생 가능 → sys.setrecursionlimit() 쓰거나 반복 스택 구현 권장.
- queue를 list + pop(0)로 구현
- pop(0)은 O(n) → collections.deque 사용 (popleft O(1)).
- 인접리스트 초기화 버그
- graph = [[]] * n 쓰면 모든 행이 같은 리스트를 참조 → graph = [[] for _ in range(n)] 사용.
- 연결되지 않은 그래프
- 하나의 start로 전체 노드가 커버되지 않음 → 모든 정점에 대해 아직 방문하지 않았으면 반복적으로 dfs/bfs 호출.
- 방향 그래프/무방향 그래프 혼동
- 무방향이면 양쪽에 간선 추가(g[u].append(v); g[v].append(u)).
요약(핵심만)
- BFS = 큐 + 레벨 단위 방문 + 비가중 최단경로 보장.
- DFS = 스택/재귀 + 가능한 깊게 방문 + 사이클 검출, 위상 정렬 등에 유리.
- 둘 다 시간복잡도 O(V + E), visited 관리는 필수.
