[2026] BFS와 DFS | 그래프 탐색 알고리즘 완벽 정리
![[2026] BFS와 DFS | 그래프 탐색 알고리즘 완벽 정리](/og/s/algorithm-series-10-bfs-dfs.webp)
이 글의 핵심
BFS와 DFS: 그래프 탐색 알고리즘 BFS (너비 우선 탐색)·DFS (깊이 우선 탐색).
들어가며
”그래프 탐색의 양대 산맥”
BFS와 DFS는 그래프/트리 탐색의 기본입니다. 코딩 테스트에서 매우 자주 나오므로 반드시 마스터해야 합니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
사전 지식 (초보자를 위한 기초)
1. 그래프(Graph)란?
그래프는 점(노드)과 선(간선)으로 이루어진 자료구조입니다. 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
예시: 친구 관계 그래프
철수 ─── 영희
│ │
민수 ─── 지수
노드(Node): 철수, 영희, 민수, 지수 (사람)
간선(Edge): 친구 관계를 나타내는 선그래프의 종류: 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 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)란?
트리는 사이클이 없는 그래프입니다. 부모-자식 관계로 이루어져 있습니다. 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
예시: 가족 관계 트리
할아버지
/ \
아빠 삼촌
/ \
나 동생
특징:
- 루트(Root): 최상위 노드 (할아버지)
- 부모(Parent): 위 노드 (아빠)
- 자식(Child): 아래 노드 (나, 동생)
- 리프(Leaf): 자식이 없는 노드 (나, 동생, 삼촌)3. 탐색(Traversal)이란?
탐색은 모든 노드를 한 번씩 방문하는 것입니다. 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
예시: 미로 탈출
S ─ □ ─ □
│ │ │
□ ─ □ ─ E
S: 시작점
E: 도착점
□: 갈 수 있는 곳
탐색: S에서 시작해서 E를 찾기4. 큐(Queue)와 스택(Stack) 복습
큐 (Queue) - 선입선출 (FIFO) 아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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) 아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 (너비 우선 탐색) - 넓게 퍼지기 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
물결이 퍼지는 모습:
시작점에 돌을 던지면
물결이 동심원으로 퍼짐
1 (시작)
/ \
2 3 (1단계)
/ \ \
4 5 6 (2단계)
방문 순서: 1 → 2 → 3 → 4 → 5 → 6
(가까운 것부터 차례대로)DFS (깊이 우선 탐색) - 깊게 파고들기 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
미로를 탐험하는 모습:
한 방향으로 끝까지 가고
막히면 되돌아와서 다른 길 시도
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는 시작점에서 가까운 층부터 넓게 퍼지며 방문합니다. 연못에 돌을 던졌을 때 물결이 바깥으로 퍼지는 모습과 비슷하고, 가중치 없는 그래프에서는 최단 거리를 구할 때 자주 씁니다. 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
1
/ \
2 3
/ \
4 5
BFS 순서: 1 → 2 → 3 → 4 → 5 (레벨별)Python 구현
BFS는 큐(Queue)를 사용하여 레벨별로 탐색합니다: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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보다 많을 수 있음 (넓은 그래프)
최단 경로 (거리 계산)
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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는 한 방향으로 끝까지 들어갔다가, 더 갈 곳이 없으면 이전 갈림길로 돌아옵니다. 미로에서 한쪽 벽만 따라 가다 막히면 되돌아가는 탐색과 같습니다. 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
1
/ \
2 3
/ \
4 5
DFS 순서: 1 → 2 → 4 → 5 → 3 (깊이 우선)Python 구현 (재귀)
DFS는 재귀 또는 스택을 사용하여 깊이 우선으로 탐색합니다: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 구현 (스택)
재귀 대신 명시적 스택을 사용한 반복문 구현: 다음은 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 스택 비교: 아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# 재귀 방식
# 장점: 코드 간결, 백트래킹 자연스러움
# 단점: 스택 오버플로우 위험 (깊이 제한)
# 스택 방식
# 장점: 스택 오버플로우 없음, 메모리 제어 가능
# 단점: 코드가 조금 더 복잡
# 깊이가 1000 이상이면 스택 방식 권장3. BFS vs DFS 비교
| 특징 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 | 스택/재귀 |
| 탐색 순서 | 레벨별 | 깊이 우선 |
| 최단 경로 | O | X |
| 메모리 | 많음 | 적음 |
| 구현 | 반복문 | 재귀 |
| 시간복잡도 | O(V+E) | O(V+E) |
| 언제 BFS? |
- ✅ 최단 경로
- ✅ 레벨 순회
- ✅ 가장 가까운 노드 언제 DFS?
- ✅ 모든 경로 탐색
- ✅ 백트래킹
- ✅ 사이클 검사
4. 실전 문제
문제 1: 미로 탈출 (BFS)
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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는 재귀가 간단
추천 문제
백준: