BFS와 DFS | 그래프 탐색 알고리즘 완벽 정리
이 글의 핵심
BFS와 DFS에 대한 실전 가이드입니다. 그래프 탐색 알고리즘 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며
”그래프 탐색의 양대 산맥”
BFS와 DFS는 그래프/트리 탐색의 기본입니다. 코딩 테스트에서 매우 자주 나오므로 반드시 마스터해야 합니다.
사전 지식 (초보자를 위한 기초)
1. 그래프(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': []
}2. 트리(Tree)란?
트리는 사이클이 없는 그래프입니다. 부모-자식 관계로 이루어져 있습니다.
예시: 가족 관계 트리
할아버지
/ \
아빠 삼촌
/ \
나 동생
특징:
- 루트(Root): 최상위 노드 (할아버지)
- 부모(Parent): 위 노드 (아빠)
- 자식(Child): 아래 노드 (나, 동생)
- 리프(Leaf): 자식이 없는 노드 (나, 동생, 삼촌)3. 탐색(Traversal)이란?
탐색은 모든 노드를 한 번씩 방문하는 것입니다.
예시: 미로 탈출
S ─ □ ─ □
│ │ │
□ ─ □ ─ E
S: 시작점
E: 도착점
□: 갈 수 있는 곳
탐색: S에서 시작해서 E를 찾기4. 큐(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
# 비유: 접시 쌓기
# 나중에 올린 접시를 먼저 꺼냄5. 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
(한 길을 끝까지 간 후 다음 길)6. 언제 BFS를, 언제 DFS를 사용할까?
BFS 사용 시기:
- 최단 거리 찾기
- 레벨별 탐색
- 가장 가까운 노드 찾기
# 예시: 미로 최단 거리
# BFS는 가까운 곳부터 탐색하므로
# 처음 도착점에 도달하면 그게 최단 거리!DFS 사용 시기:
- 모든 경로 탐색
- 백트래킹 (순열, 조합)
- 사이클 검사
# 예시: 모든 경로 찾기
# DFS는 한 경로를 끝까지 탐색하므로
# 모든 가능한 경로를 찾을 수 있음비교표:
| 특징 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 (Queue) | 스택 (Stack) / 재귀 |
| 탐색 방식 | 넓게 (레벨별) | 깊게 (한 방향) |
| 최단 거리 | ✅ 가능 | ❌ 불가능 |
| 메모리 | 많이 사용 | 적게 사용 |
| 구현 | 반복문 | 재귀 (더 간단) |
1. 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보다 많을 수 있음 (넓은 그래프)
최단 경로 (거리 계산)
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)2. 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 이상이면 스택 방식 권장3. BFS vs DFS 비교
| 특징 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 | 스택/재귀 |
| 탐색 순서 | 레벨별 | 깊이 우선 |
| 최단 경로 | O | X |
| 메모리 | 많음 | 적음 |
| 구현 | 반복문 | 재귀 |
| 시간복잡도 | O(V+E) | O(V+E) |
언제 BFS?
- ✅ 최단 경로
- ✅ 레벨 순회
- ✅ 가장 가까운 노드
언제 DFS?
- ✅ 모든 경로 탐색
- ✅ 백트래킹
- ✅ 사이클 검사
4. 실전 문제
문제 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)) # 9문제 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정리
핵심 요약
- BFS: 큐 사용, 최단 경로, O(V+E)
- DFS: 스택/재귀, 모든 경로, O(V+E)
- 선택 기준: 최단 경로 → BFS, 모든 경로 → DFS
- 구현: BFS는 큐, DFS는 재귀가 간단
추천 문제
백준:
프로그래머스:
관련 글
- 그래프 자료구조 | 인접 리스트, 인접 행렬, 탐색 완벽 정리
- 알고리즘 시리즈 전체 목차
- 배열과 리스트
- 스택과 큐