BFS와 DFS: 큐·재귀로 구현하는 그래프 탐색과 최단 거리·연결 요소 문제
이 글의 핵심
그래프, 트리, 큐와 스택 같은 기초 개념을 먼저 정리한 뒤 두 탐색이 방문 순서에서 어떻게 달라지는지 직관적으로 보여 줍니다. 언제 BFS를 쓰고 언제 DFS를 쓰는지 판단 기준을 세우고, 재귀 DFS가 RecursionError로 실패할 때 스택 기반 구현으로 바꾸는 방법까지 다룹니다.
시리즈 안내
들어가며
BFS와 DFS는 그래프/트리 탐색의 기본입니다. 코딩 테스트에서 자주 나오며, 이 글에서는 두 탐색이 방문 순서에서 어떻게 다른지와 최단 거리·경로 탐색·사이클 검사 중 어디에 어느 쪽을 쓰는지를 Python 예제로 정리합니다.
사전 지식 (초보자를 위한 기초)
그래프(Graph)란?
그래프는 점(노드)과 선(간선)으로 이루어진 자료구조입니다.
예시: 친구 관계 그래프
철수 ─── 영희
│ │
민수 ─── 지수
노드(Node): 철수, 영희, 민수, 지수 (사람)
간선(Edge): 친구 관계를 나타내는 선그래프의 종류:
# 1. 무방향 그래프 (양방향)
# A ─ B (A → B, B → A 모두 가능)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
# 2. 방향 그래프 (단방향)
# A → B (A에서 B로만 가능)
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': [],
'D': []
}트리(Tree)란?
트리는 사이클이 없는 그래프입니다. 부모-자식 관계로 이루어져 있습니다.
예시: 가족 관계 트리
할아버지
/ \
아빠 삼촌
/ \
나 동생
특징:
- 루트(Root): 최상위 노드 (할아버지)
- 부모(Parent): 위 노드 (아빠)
- 자식(Child): 아래 노드 (나, 동생)
- 리프(Leaf): 자식이 없는 노드 (나, 동생, 삼촌)탐색(Traversal)이란?
탐색은 모든 노드를 한 번씩 방문하는 것입니다.
예시: 미로 탈출
S ─ □ ─ □
│ │ │
□ ─ □ ─ E
S: 시작점
E: 도착점
□: 갈 수 있는 곳
탐색: S에서 시작해서 E를 찾기큐(Queue)와 스택(Stack) 복습
큐 (Queue) - 선입선출 (FIFO)
from collections import deque
queue = deque()
queue.append(1) # 뒤에 추가
queue.append(2)
queue.append(3)
print(queue.popleft()) # 1 (앞에서 제거)
print(queue.popleft()) # 2
print(queue.popleft()) # 3
# 비유: 줄 서기
# 먼저 온 사람이 먼저 나감스택 (Stack) - 후입선출 (LIFO)
stack = []
stack.append(1) # 위에 추가
stack.append(2)
stack.append(3)
print(stack.pop()) # 3 (위에서 제거)
print(stack.pop()) # 2
print(stack.pop()) # 1
# 비유: 접시 쌓기
# 나중에 올린 접시를 먼저 꺼냄BFS vs DFS 직관적 이해
BFS (너비 우선 탐색) - 넓게 퍼지기
물결이 퍼지는 모습:
시작점에 돌을 던지면
물결이 동심원으로 퍼짐
1 (시작)
/ \
2 3 (1단계)
/ \ \
4 5 6 (2단계)
방문 순서: 1 → 2 → 3 → 4 → 5 → 6
(가까운 것부터 차례대로)DFS (깊이 우선 탐색) - 깊게 파고들기
미로를 탐험하는 모습:
한 방향으로 끝까지 가고
막히면 되돌아와서 다른 길 시도
1 (시작)
/ \
2 5
/ \
3 4
방문 순서: 1 → 2 → 3 → 4 → 5
(한 길을 끝까지 간 후 다음 길)언제 BFS를, 언제 DFS를 사용할까?
BFS 사용 시기:
- 최단 거리 찾기
- 레벨별 탐색
- 가장 가까운 노드 찾기
# 예시: 미로 최단 거리
# BFS는 가까운 곳부터 탐색하므로
# 처음 도착점에 도달하면 그게 최단 거리!DFS 사용 시기:
- 모든 경로 탐색
- 백트래킹 (순열, 조합)
- 사이클 검사
# 예시: 모든 경로 찾기
# DFS는 한 경로를 끝까지 탐색하므로
# 모든 가능한 경로를 찾을 수 있음비교표:
| 특징 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 (Queue) | 스택 (Stack) / 재귀 |
| 탐색 방식 | 넓게 (레벨별) | 깊게 (한 방향) |
| 최단 거리 | ✅ 가능 | ❌ 불가능 |
| 메모리 | 많이 사용 | 적게 사용 |
| 구현 | 반복문 | 재귀 (더 간단) |
BFS (너비 우선 탐색)
BFS란?
BFS는 시작점에서 가까운 층부터 넓게 퍼지며 방문합니다. 연못에 돌을 던졌을 때 물결이 바깥으로 퍼지는 모습과 비슷하며, 가중치 없는 그래프에서는 최단 거리를 구할 때 자주 씁니다.
1
/ \
2 3
/ \
4 5
BFS 순서: 1 → 2 → 3 → 4 → 5 (레벨별)Python 구현
BFS는 큐(Queue)를 사용하여 레벨별로 탐색합니다:
from collections import deque
def bfs(graph, start):
# visited: 방문한 노드 집합 (중복 방문 방지)
visited = set()
# queue: 방문할 노드를 저장하는 큐 (FIFO)
# deque 사용 이유: popleft()가 O(1) (list.pop(0)은 O(n))
queue = deque([start])
# 시작 노드를 방문 처리
visited.add(start)
# 탐색 결과를 저장할 리스트
result = []
# 큐가 빌 때까지 반복
while queue:
# 큐의 맨 앞 노드를 꺼냄 (FIFO)
node = queue.popleft()
# 노드 방문 처리
result.append(node)
# 현재 노드의 모든 이웃 노드 확인
for neighbor in graph[node]:
# 아직 방문하지 않은 노드만 처리
if neighbor not in visited:
# 방문 처리 (중복 방지)
visited.add(neighbor)
# 큐에 추가 (나중에 방문)
queue.append(neighbor)
return result
# 그래프 (인접 리스트 표현)
# 각 노드의 이웃 노드들을 리스트로 저장
graph = {
1: [2, 3], # 노드 1은 2, 3과 연결
2: [1, 4, 5], # 노드 2는 1, 4, 5와 연결
3: [1], # 노드 3은 1과 연결
4: [2], # 노드 4는 2와 연결
5: [2] # 노드 5는 2와 연결
}
print(bfs(graph, 1)) # [1, 2, 3, 4, 5]
# 탐색 과정 (start=1):
# 초기: queue=[1], visited={1}
#
# 1단계: node=1 꺼냄
# - 이웃: 2, 3
# - queue=[2, 3], visited={1, 2, 3}
# - result=[1]
#
# 2단계: node=2 꺼냄
# - 이웃: 1(방문함), 4, 5
# - queue=[3, 4, 5], visited={1, 2, 3, 4, 5}
# - result=[1, 2]
#
# 3단계: node=3 꺼냄
# - 이웃: 1(방문함)
# - queue=[4, 5], visited={1, 2, 3, 4, 5}
# - result=[1, 2, 3]
#
# 4단계: node=4 꺼냄
# - 이웃: 2(방문함)
# - queue=[5], visited={1, 2, 3, 4, 5}
# - result=[1, 2, 3, 4]
#
# 5단계: node=5 꺼냄
# - 이웃: 2(방문함)
# - queue=[], visited={1, 2, 3, 4, 5}
# - result=[1, 2, 3, 4, 5]
#
# 큐가 비었으므로 종료BFS의 특징:
- 레벨별로 탐색 (가까운 노드부터)
- 최단 경로 보장 (가중치 없는 그래프)
- 큐 사용 (FIFO)
- 메모리 사용량이 DFS보다 많을 수 있음 (넓은 그래프)
최단 경로 (거리 계산)
BFS가 최단 거리를 보장하는 이유는 큐의 순서에 있습니다. 시작점에서 거리 0인 노드가 먼저 큐에 들어가고, 그 노드들이 꺼내지면서 거리 1인 노드들이 뒤에 붙고, 거리 1인 노드들이 모두 꺼내진 뒤에야 거리 2인 노드들이 나옵니다. 즉 큐 안에는 항상 거리 d인 노드들 뒤에 거리 d+1인 노드들만 있으므로, 어떤 노드가 처음 발견되는 순간의 거리가 최단 거리입니다. 아래 코드가 visited 딕셔너리에 거리를 한 번만 기록하고 다시 고치지 않는 것도 이 성질 덕분입니다.
def bfs_shortest_path(graph, start, end):
visited = {start: 0} # 노드: 거리
queue = deque([start])
while queue:
node = queue.popleft()
if node == end:
return visited[end]
for neighbor in graph[node]:
if neighbor not in visited:
visited[neighbor] = visited[node] + 1
queue.append(neighbor)
return -1 # 경로 없음
# 테스트
print(bfs_shortest_path(graph, 1, 4)) # 2 (1→2→4)이 성질은 모든 간선의 비용이 같을 때만 성립한다는 점을 꼭 기억해야 합니다. 간선마다 비용이 다르면 간선 수가 적은 경로가 더 비쌀 수 있어서, 먼저 발견한 거리가 최단이라는 보장이 깨집니다. 비용이 0과 1 두 종류뿐이면 비용 0 간선은 appendleft, 비용 1 간선은 append로 넣는 0-1 BFS로 해결할 수 있고, 그 밖의 음이 아닌 가중치는 다익스트라(우선순위 큐)가 필요합니다. 코딩 테스트에서 “순간이동은 0초, 걷기는 1초” 같은 조건이 나오면(백준 13549번) 평범한 BFS로 풀었다가 틀리는 경우가 많은데, 바로 이 전제가 깨졌기 때문입니다.
경로 자체가 필요할 때는 거리 대신 parent[neighbor] = node처럼 “어디서 왔는지”를 기록해 두고, 도착점에서 parent를 따라 거꾸로 올라간 뒤 뒤집으면 됩니다. 여러 출발점에서 동시에 퍼지는 문제(토마토 익히기, 불 번지기 등)는 시작 노드들을 전부 처음부터 큐에 넣고 거리 0으로 시작하는 멀티 소스 BFS로 풀며, 출발점마다 BFS를 따로 돌리면 시간 복잡도가 출발점 수만큼 곱해집니다.
DFS (깊이 우선 탐색)
DFS란?
DFS는 한 방향으로 끝까지 들어갔다가, 더 갈 곳이 없으면 이전 갈림길로 돌아옵니다. 미로에서 한쪽 벽만 따라 가다 막히면 되돌아가는 탐색과 같습니다.
1
/ \
2 3
/ \
4 5
DFS 순서: 1 → 2 → 4 → 5 → 3 (깊이 우선)Python 구현 (재귀)
DFS는 재귀 또는 스택을 사용하여 깊이 우선으로 탐색합니다:
def dfs_recursive(graph, node, visited, result):
# 현재 노드를 방문 처리
visited.add(node)
result.append(node)
# 현재 노드의 모든 이웃 노드를 확인
for neighbor in graph[node]:
# 아직 방문하지 않은 노드만 재귀 호출
if neighbor not in visited:
# 재귀: 이웃 노드부터 끝까지 탐색
# 백트래킹: 끝까지 갔다가 돌아옴
dfs_recursive(graph, neighbor, visited, result)
# 사용
visited = set() # 방문한 노드 집합
result = [] # 탐색 순서
dfs_recursive(graph, 1, visited, result)
print(result) # [1, 2, 4, 5, 3]
# 탐색 과정 (start=1):
# 1. dfs(1) 호출
# - visited={1}, result=[1]
# - 이웃: 2, 3
# - 2부터 재귀
#
# 2. dfs(2) 호출 (1의 첫 번째 이웃)
# - visited={1, 2}, result=[1, 2]
# - 이웃: 1(방문함), 4, 5
# - 4부터 재귀
#
# 3. dfs(4) 호출 (2의 첫 번째 미방문 이웃)
# - visited={1, 2, 4}, result=[1, 2, 4]
# - 이웃: 2(방문함)
# - 더 이상 미방문 노드 없음 → 백트랙
#
# 4. dfs(2)로 복귀
# - 다음 이웃: 5
# - 5 재귀
#
# 5. dfs(5) 호출
# - visited={1, 2, 4, 5}, result=[1, 2, 4, 5]
# - 이웃: 2(방문함)
# - 백트랙
#
# 6. dfs(2)로 복귀 → dfs(1)로 복귀
# - 다음 이웃: 3
# - 3 재귀
#
# 7. dfs(3) 호출
# - visited={1, 2, 3, 4, 5}, result=[1, 2, 4, 5, 3]
# - 이웃: 1(방문함)
# - 백트랙
#
# 8. 모든 재귀 종료재귀의 장점:
-
코드가 간결하고 직관적
-
백트래킹 구현이 자연스러움 재귀의 단점:
-
깊이가 깊으면 스택 오버플로우 위험
-
Python 기본 재귀 한도: 1000 (
sys.setrecursionlimit로 변경 가능)
Python 구현 (스택)
재귀 대신 명시적 스택을 사용한 반복문 구현:
def dfs_iterative(graph, start):
visited = set() # 방문한 노드 집합
stack = [start] # 스택 (LIFO) - Python list 사용
result = [] # 탐색 순서
# 스택이 빌 때까지 반복
while stack:
# 스택의 맨 위 노드를 꺼냄 (LIFO)
node = stack.pop()
# 이미 방문한 노드는 건너뜀
if node not in visited:
# 노드 방문 처리
visited.add(node)
result.append(node)
# 이웃 노드들을 스택에 추가
# reversed(): 작은 번호부터 방문하기 위해 역순 추가
# (스택은 LIFO이므로 나중에 추가된 것이 먼저 나옴)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
print(dfs_iterative(graph, 1)) # [1, 2, 4, 5, 3]
# 탐색 과정 (start=1):
# 초기: stack=[1], visited={}
#
# 1단계: node=1 꺼냄
# - visited={1}, result=[1]
# - 이웃: [2, 3]
# - reversed([2, 3]) = [3, 2]
# - stack=[3, 2] (2가 위에)
#
# 2단계: node=2 꺼냄 (스택 맨 위)
# - visited={1, 2}, result=[1, 2]
# - 이웃: [1, 4, 5]
# - 1은 방문함, [4, 5] 추가
# - reversed([4, 5]) = [5, 4]
# - stack=[3, 5, 4] (4가 위에)
#
# 3단계: node=4 꺼냄
# - visited={1, 2, 4}, result=[1, 2, 4]
# - 이웃: [2] (방문함)
# - stack=[3, 5]
#
# 4단계: node=5 꺼냄
# - visited={1, 2, 4, 5}, result=[1, 2, 4, 5]
# - 이웃: [2] (방문함)
# - stack=[3]
#
# 5단계: node=3 꺼냄
# - visited={1, 2, 3, 4, 5}, result=[1, 2, 4, 5, 3]
# - 이웃: [1] (방문함)
# - stack=[]
#
# 스택이 비었으므로 종료재귀 vs 스택 비교:
# 재귀 방식
# 장점: 코드 간결, 백트래킹 자연스러움
# 단점: 스택 오버플로우 위험 (깊이 제한)
# 스택 방식
# 장점: 스택 오버플로우 없음, 메모리 제어 가능
# 단점: 코드가 조금 더 복잡
# 깊이가 1000 이상이면 스택 방식 권장반복 DFS에는 알아 두어야 할 미묘한 차이가 있습니다. 위 구현은 꺼낼 때 방문 여부를 검사하므로 같은 노드가 스택에 여러 번 들어갈 수 있고, 그 대신 방문 순서가 재귀 DFS와 똑같이 나옵니다. BFS처럼 넣을 때 방문 처리를 하면 스택 크기는 줄지만 방문 순서가 재귀 버전과 달라져서, “DFS 방문 순서를 출력하라”는 문제(백준 1260번 등)에서 오답이 됩니다. 순서가 중요하면 이 글의 방식을, 순서는 상관없고 메모리가 중요하면 넣을 때 방문 처리하는 방식을 고르면 됩니다.
비교표의 “메모리: DFS가 적다”도 조건부입니다. DFS의 메모리는 그래프의 깊이에, BFS의 메모리는 한 레벨의 너비에 비례합니다. 가지가 넓게 퍼지는 트리에서는 DFS가 유리하지만, 한 줄로 길게 이어진 그래프에서는 DFS 스택이 노드 수만큼 커집니다.
BFS vs DFS 비교
| 특징 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 | 스택/재귀 |
| 탐색 순서 | 레벨별 | 깊이 우선 |
| 최단 경로 | O | X |
| 메모리 | 많음 | 적음 |
| 구현 | 반복문 | 재귀 |
| 시간복잡도 | O(V+E) | O(V+E) |
언제 BFS?
- 최단 경로
- 레벨 순회
- 가장 가까운 노드 언제 DFS?
- 모든 경로 탐색
- 백트래킹
- 사이클 검사
실전 문제
문제 1: 미로 탈출 (BFS)
from collections import deque
def maze_escape(maze):
"""
(0,0)에서 (n-1,m-1)까지 최단 거리
1: 이동 가능, 0: 벽
"""
n, m = len(maze), len(maze[0])
queue = deque([(0, 0, 1)]) # (행, 열, 거리)
visited = {(0, 0)}
# 상하좌우
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while queue:
r, c, dist = queue.popleft()
if r == n-1 and c == m-1:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < n and 0 <= nc < m and
maze[nr][nc] == 1 and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
# 테스트
maze = [
[1, 0, 1, 1, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 1, 1, 0, 1]
]
print(maze_escape(maze)) # 14 (시작 칸 포함, 벽을 돌아가는 유일한 경로)거리를 큐 원소 (행, 열, 거리)에 같이 넣은 이유는 BFS가 “큐에서 먼저 나온 칸일수록 시작점에서 가깝다”는 성질을 갖기 때문입니다. 같은 거리의 칸들이 모두 처리된 뒤에야 거리+1인 칸들이 나오므로, 도착점을 처음 꺼내는 순간의 dist가 곧 최단 거리이고 더 탐색할 필요 없이 바로 반환해도 됩니다. 반대로 DFS로 같은 문제를 풀면 처음 도착한 경로가 최단이라는 보장이 없어 모든 경로를 끝까지 비교해야 하고, 격자가 조금만 커져도 경우의 수가 폭발합니다.
이 코드에서 가장 중요한 한 줄은 visited.add((nr, nc))를 큐에 넣는 시점에 한다는 점입니다. 처음 BFS를 짤 때 흔히 하는 실수는 큐에서 꺼낼 때 방문 처리를 하는 것인데, 그러면 같은 칸이 여러 이웃에게서 중복으로 큐에 들어갑니다. 결과는 여전히 맞게 나오지만 큐가 불필요하게 커져서, 백준 2178번 같은 문제에서는 시간 초과나 메모리 초과로 이어지곤 합니다. 거리 배열을 따로 두고 dist[nr][nc] == 0으로 방문 여부를 겸하는 방식도 자주 쓰이는데, 이 경우 시작 칸을 1로 초기화해 두지 않으면 시작점을 다시 방문하는 버그가 생깁니다.
문제 2: 섬의 개수 (DFS)
def count_islands(grid):
"""
1로 연결된 영역의 개수
"""
if not grid:
return 0
n, m = len(grid), len(grid[0])
visited = set()
count = 0
def dfs(r, c):
if (r < 0 or r >= n or c < 0 or c >= m or
grid[r][c] == 0 or (r, c) in visited):
return
visited.add((r, c))
# 상하좌우 탐색
dfs(r-1, c)
dfs(r+1, c)
dfs(r, c-1)
dfs(r, c+1)
for i in range(n):
for j in range(m):
if grid[i][j] == 1 and (i, j) not in visited:
dfs(i, j)
count += 1
return count
# 테스트
grid = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]
]
print(count_islands(grid)) # 3바깥 이중 루프가 “아직 방문하지 않은 육지”를 만날 때마다 dfs를 한 번 호출하고, 그 한 번의 호출이 연결된 육지 전체를 방문 처리합니다. 그래서 dfs가 호출된 횟수가 곧 섬(연결 요소)의 개수입니다. 이 문제에서 DFS를 고른 것은 최단 거리가 필요 없고 “연결된 칸을 모두 칠하기”만 하면 되기 때문인데, 사실 BFS로 바꿔도 결과와 시간 복잡도(O(n·m))는 같습니다. 연결 요소 세기는 둘 중 무엇을 써도 되는 대표적인 경우이며, 구현이 짧은 쪽을 고르면 됩니다.
주의할 점은 재귀 깊이입니다. 격자 전체가 1로 채워진 1000×1000 입력이라면 재귀가 최악의 경우 수십만 단계까지 들어가고, Python에서는 “RecursionError: maximum recursion depth exceeded”가 납니다. sys.setrecursionlimit(10**6)으로 한도를 올리면 이 에러는 사라지지만, 이번에는 C 스택이 먼저 바닥나 에러 메시지 없이 프로세스가 종료되는 경우가 있습니다. 채점 환경에서 “런타임 에러”만 뜨고 원인을 알 수 없다면 대개 이 경우이므로, 큰 격자에서는 처음부터 stack 리스트를 쓰는 반복 DFS나 BFS로 작성하는 편이 안전합니다. 또 visited를 튜플 집합으로 두는 대신 grid[r][c] = 0으로 방문한 칸을 지워 나가면 해시 연산이 줄어 체감될 만큼 빨라지지만, 입력 격자를 훼손한다는 점은 감안해야 합니다.
추천 문제와 방문 처리 시점
BFS에서 가장 흔한 실수는 방문 표시를 큐에서 꺼낼 때 하는 것입니다. 그러면 같은 칸이 아직 처리되기 전에 여러 이웃에서 중복으로 큐에 들어가서, 격자 문제에서는 큐 크기가 불어나 시간·메모리 초과가 납니다. 방문 표시는 큐에 넣는 순간 해야 합니다. 미로 탐색(2178번)처럼 “최소 칸 수”를 묻는 문제는 DFS로도 답은 나오지만 모든 경로를 다 봐야 하므로 BFS로 푸는 것이 맞고, 단지번호붙이기(2667번)처럼 연결된 덩어리 수를 세는 문제는 어느 쪽이든 괜찮습니다. Python에서 재귀 DFS를 쓸 때는 격자가 커지면 재귀 한도에 걸리므로 sys.setrecursionlimit을 함께 설정하세요.
백준:
프로그래머스:
자주 묻는 질문 (FAQ)
Q. Python에서 재귀 DFS가 RecursionError로 실패하면 어떻게 하나요?
A. Python의 기본 재귀 한도는 1000 정도라서, 격자가 크거나 한 줄로 길게 이어진 그래프에서는 재귀 DFS가 쉽게 한도를 넘습니다. sys.setrecursionlimit으로 한도를 올리는 방법이 있지만, 더 안전한 방법은 명시적 스택을 쓰는 반복문 DFS로 바꾸는 것입니다. 최단 거리가 목적이라면 애초에 큐 기반 BFS를 쓰는 편이 재귀 깊이 문제도 피할 수 있습니다.