Updated Feb 6, 2026
들어가며
그래프 탐색은 코딩 테스트에서 가장 빈번하게 출제되는 주제 중 하나입니다. BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 그래프의 모든 노드를 방문하는 기본 알고리즘이며, 최단 경로, 연결 요소 찾기, 미로 탐색 등 다양한 문제에 응용됩니다.
이 글에서는 BFS/DFS의 핵심 원리부터 시작해 실전 구현, 시간 복잡도 분석, 그리고 난이도별 문제 접근법까지 완벽하게 정복해보겠습니다.
그래프 기본 개념
그래프란?
그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조입니다.
- 노드: 데이터를 저장하는 지점
- 간선: 노드 간의 연결 관계
그래프 표현 방법
| 표현 방식 | 공간 복잡도 | 간선 존재 확인 | 모든 인접 노드 탐색 | 특징 |
|---|---|---|---|---|
| 인접 행렬 | 밀집 그래프에 유리 | |||
| 인접 리스트 | 희소 그래프에 유리 |
여기서 는 노드(정점) 수, 는 간선 수를 의미합니다.
# 인접 리스트 표현 (가장 많이 사용)
graph = {
1: [2, 3, 4],
2: [1, 5],
3: [1],
4: [1, 6],
5: [2],
6: [4]
}
# 인접 행렬 표현
matrix = [
[0, 1, 1, 1, 0, 0], # 노드 1
[1, 0, 0, 0, 1, 0], # 노드 2
[1, 0, 0, 0, 0, 0], # 노드 3
[1, 0, 0, 0, 0, 1], # 노드 4
[0, 1, 0, 0, 0, 0], # 노드 5
[0, 0, 0, 1, 0, 0], # 노드 6
]
핵심 포인트: 코딩 테스트에서는 대부분 인접 리스트를 사용합니다. 메모리 효율이 좋고 인접 노드 탐색이 빠르기 때문입니다.
DFS (깊이 우선 탐색)
DFS 핵심 원리
DFS는 한 방향으로 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식입니다.
동작 방식:
1. 시작 노드를 방문하고 방문 표시
2. 인접한 미방문 노드 중 하나를 선택해 재귀적으로 방문
3. 더 이상 방문할 노드가 없으면 이전 노드로 백트래킹
4. 모든 노드를 방문할 때까지 반복
자료구조: 스택(Stack) 또는 재귀 함수
DFS 구현 (재귀)
def dfs_recursive(graph, node, visited):
"""
재귀를 이용한 DFS 구현
Args:
graph: 인접 리스트로 표현된 그래프
node: 현재 방문 중인 노드
visited: 방문 여부를 기록하는 집합
"""
visited.add(node) # 현재 노드 방문 표시
print(node, end=' ') # 방문 순서 출력
# 인접한 모든 노드에 대해
for neighbor in graph[node]:
if neighbor not in visited: # 미방문 노드라면
dfs_recursive(graph, neighbor, visited) # 재귀 호출
# 실행 예제
graph = {
1: [2, 3, 4],
2: [1, 5],
3: [1],
4: [1, 6],
5: [2],
6: [4]
}
visited = set()
dfs_recursive(graph, 1, visited)
# 출력: 1 2 5 3 4 6
DFS 구현 (스택)
def dfs_stack(graph, start):
"""
스택을 이용한 DFS 구현
Args:
graph: 인접 리스트로 표현된 그래프
start: 시작 노드
"""
visited = set() # 방문한 노드 기록
stack = [start] # 스택 초기화
while stack:
node = stack.pop() # 스택에서 노드 꺼내기
if node not in visited:
visited.add(node) # 방문 표시
print(node, end=' ') # 방문 순서 출력
# 인접 노드를 스택에 추가 (역순으로 추가하면 작은 번호부터 방문)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
# 실행 예제
dfs_stack(graph, 1)
# 출력: 1 2 5 3 4 6
DFS 시간/공간 복잡도
- 시간 복잡도:
- 모든 노드()를 한 번씩 방문
- 모든 간선()을 한 번씩 확인
- 공간 복잡도:
- 방문 체크 배열:
- 재귀 호출 스택 (최악의 경우 모든 노드가 일렬):
BFS (너비 우선 탐색)
BFS 핵심 원리
BFS는 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방식입니다.
동작 방식:
1. 시작 노드를 큐에 넣고 방문 표시
2. 큐에서 노드를 꺼내 인접한 모든 미방문 노드를 큐에 추가
3. 큐가 빌 때까지 2번 반복
자료구조: 큐(Queue)
핵심 포인트: BFS는 최단 경로를 보장합니다. 가중치가 없는 그래프에서 시작 노드부터 각 노드까지의 최단 거리를 구할 때 사용합니다.
BFS 구현
from collections import deque
def bfs(graph, start):
"""
큐를 이용한 BFS 구현
Args:
graph: 인접 리스트로 표현된 그래프
start: 시작 노드
"""
visited = set() # 방문한 노드 기록
queue = deque([start]) # 큐 초기화
visited.add(start) # 시작 노드 방문 표시
while queue:
node = queue.popleft() # 큐에서 노드 꺼내기 (FIFO)
print(node, end=' ') # 방문 순서 출력
# 인접한 모든 노드에 대해
for neighbor in graph[node]:
if neighbor not in visited: # 미방문 노드라면
visited.add(neighbor) # 방문 표시
queue.append(neighbor) # 큐에 추가
# 실행 예제
graph = {
1: [2, 3, 4],
2: [1, 5],
3: [1],
4: [1, 6],
5: [2],
6: [4]
}
bfs(graph, 1)
# 출력: 1 2 3 4 5 6
BFS로 최단 거리 구하기
from collections import deque
def bfs_shortest_path(graph, start, target):
"""
BFS를 이용해 최단 거리 계산
Args:
graph: 인접 리스트로 표현된 그래프
start: 시작 노드
target: 목표 노드
Returns:
최단 거리 (도달 불가능하면 -1)
"""
visited = {start} # 방문한 노드 기록
queue = deque([(start, 0)]) # (노드, 거리) 튜플 저장
while queue:
node, distance = queue.popleft()
# 목표 노드에 도달하면 거리 반환
if node == target:
return distance
# 인접 노드 탐색
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1)) # 거리 증가
return -1 # 도달 불가능
# 실행 예제
print(bfs_shortest_path(graph, 1, 6)) # 출력: 2
print(bfs_shortest_path(graph, 1, 5)) # 출력: 2
BFS 시간/공간 복잡도
- 시간 복잡도:
- 모든 노드()를 한 번씩 방문
- 모든 간선()을 한 번씩 확인
- 공간 복잡도:
- 방문 체크 집합:
- 큐 (최악의 경우 모든 노드 저장):
BFS vs DFS 비교
| 비교 항목 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 (Queue) | 스택 (Stack) / 재귀 |
| 탐색 방식 | 가까운 노드부터 (레벨 순) | 한 방향 끝까지 (깊이 순) |
| 최단 경로 | 보장 (가중치 없는 그래프) | 보장 안 됨 |
| 메모리 사용 | 많음 (같은 레벨 노드 저장) | 적음 (경로 상 노드만 저장) |
| 구현 난이도 | 쉬움 (반복문) | 쉬움 (재귀) |
| 사용 사례 | 최단 거리, 레벨별 탐색 | 경로 탐색, 사이클 검출, 위상 정렬 |
선택 기준: 최단 경로가 필요하면 BFS, 모든 경로 탐색이나 백트래킹이 필요하면 DFS
실전 문제 유형별 접근법
1. 최단 거리 문제 (난이도: 쉬움)
대표 문제: 미로 탈출, 바이러스 확산 시간
접근법: BFS + 거리 배열
from collections import deque
def maze_escape(maze):
"""
미로 탈출 최단 경로 구하기
maze[i][j]: 0은 벽, 1은 통로
(0,0)에서 (n-1, m-1)까지 최단 거리
"""
n, m = len(maze), len(maze[0])
# 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 초기화
queue = deque([(0, 0, 1)]) # (x, y, 거리)
visited = [[False] * m for _ in range(n)]
visited[0][0] = True
while queue:
x, y, dist = queue.popleft()
# 목표 지점 도달
if x == n - 1 and y == m - 1:
return dist
# 4방향 탐색
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 범위 체크 및 방문 체크
if 0 <= nx < n and 0 <= ny < m:
if maze[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx, ny, 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 또는 BFS를 여러 번 실행
def count_islands(grid):
"""
2D 그리드에서 섬의 개수 구하기
1은 땅, 0은 물
"""
if not grid:
return 0
n, m = len(grid), len(grid[0])
visited = [[False] * m for _ in range(n)]
count = 0
def dfs(x, y):
"""하나의 섬을 모두 방문 처리"""
if x < 0 or x >= n or y < 0 or y >= m:
return
if visited[x][y] or grid[x][y] == 0:
return
visited[x][y] = True
# 4방향 탐색 (상하좌우로 연결된 땅)
dfs(x - 1, y)
dfs(x + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
# 모든 칸에 대해 탐색 시작
for i in range(n):
for j in range(m):
if grid[i][j] == 1 and not visited[i][j]:
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
시간 복잡도:
3. 경로의 존재 여부 (난이도: 보통)
대표 문제: 두 노드 간 경로 존재 여부, 사이클 검출
접근법: DFS로 목표 노드까지 도달 가능한지 확인
def has_path(graph, start, target, visited=None):
"""
두 노드 사이에 경로가 존재하는지 확인
"""
if visited is None:
visited = set()
# 목표 노드 도달
if start == target:
return True
visited.add(start)
# 인접 노드 탐색
for neighbor in graph.get(start, []):
if neighbor not in visited:
if has_path(graph, neighbor, target, visited):
return True
return False
# 예제
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': ['F'],
'E': [],
'F': []
}
print(has_path(graph, 'A', 'F')) # True
print(has_path(graph, 'A', 'Z')) # False
4. 모든 경로 찾기 (난이도: 어려움)
대표 문제: 시작점에서 끝점까지 모든 경로
접근법: DFS + 백트래킹
def find_all_paths(graph, start, target, path=None):
"""
두 노드 사이의 모든 경로를 찾기
Returns:
경로 리스트의 리스트
"""
if path is None:
path = []
path = path + [start] # 현재 경로에 노드 추가
# 목표 노드 도달
if start == target:
return [path]
# 시작 노드가 그래프에 없으면
if start not in graph:
return []
paths = [] # 모든 경로 저장
# 인접 노드 탐색
for neighbor in graph[start]:
if neighbor not in path: # 사이클 방지
# 재귀적으로 경로 탐색
new_paths = find_all_paths(graph, neighbor, target, path)
paths.extend(new_paths)
return paths
# 예제
graph = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': []
}
all_paths = find_all_paths(graph, 'A', 'D')
for path in all_paths:
print(' -> '.join(path))
# 출력:
# A -> B -> C -> D
# A -> B -> D
# A -> C -> D
시간 복잡도: (최악의 경우, 완전 그래프)
5. 레벨별 탐색 (난이도: 보통)
대표 문제: 트리의 레벨 순회, 바이러스 확산 단계별 시뮬레이션
접근법: BFS + 레벨 구분
from collections import deque
def level_order_traversal(graph, start):
"""
레벨별로 노드 그룹화
Returns:
[[레벨0 노드], [레벨1 노드], ...]
"""
visited = {start}
queue = deque([start])
levels = [] # 레벨별 노드 저장
while queue:
level_size = len(queue) # 현재 레벨의 노드 개수
current_level = []
# 현재 레벨의 모든 노드 처리
for _ in range(level_size):
node = queue.popleft()
current_level.append(node)
# 다음 레벨 노드 추가
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
levels.append(current_level)
return levels
# 예제 (트리)
tree = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [],
5: [],
6: [],
7: []
}
result = level_order_traversal(tree, 1)
for i, level in enumerate(result):
print(f"Level {i}: {level}")
# 출력:
# Level 0: [1]
# Level 1: [2, 3]
# Level 2: [4, 5, 6, 7]
자주 하는 실수와 엣지 케이스
1. 방문 체크 시점 실수
# ❌ 잘못된 코드: 큐에서 꺼낼 때 방문 체크
def wrong_bfs(graph, start):
queue = deque([start])
visited = set()
while queue:
node = queue.popleft()
visited.add(node) # ← 중복 삽입 가능!
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# ✅ 올바른 코드: 큐에 넣을 때 방문 체크
def correct_bfs(graph, start):
queue = deque([start])
visited = {start} # 시작 노드 미리 체크
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # ← 큐에 넣기 전에 체크
queue.append(neighbor)
핵심: BFS에서는 큐에 넣을 때 방문 표시해야 중복 삽입을 방지할 수 있습니다.
2. 2D 그리드 범위 체크 누락
# ❌ 범위 체크 없이 접근
if maze[nx][ny] == 1: # IndexError 발생 가능
# ...
# ✅ 범위 체크 먼저
if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
# ...
3. 그래프가 비어있거나 노드가 없는 경우
def safe_dfs(graph, node, visited):
if node not in graph: # 노드가 그래프에 없을 수 있음
return
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
safe_dfs(graph, neighbor, visited)
4. 사이클이 있는 그래프
# 사이클이 있는 그래프는 반드시 visited 체크 필요
graph = {
1: [2],
2: [3],
3: [1] # ← 사이클
}
# visited 없이 DFS 하면 무한 루프!
5. 방향 그래프 vs 무방향 그래프
# 무방향 그래프는 양방향으로 간선 추가 필요
edges = [(1, 2), (2, 3), (3, 4)]
# 방향 그래프
directed_graph = {node: [] for node in range(1, 5)}
for a, b in edges:
directed_graph[a].append(b)
# 무방향 그래프
undirected_graph = {node: [] for node in range(1, 5)}
for a, b in edges:
undirected_graph[a].append(b)
undirected_graph[b].append(a) # ← 양방향 추가
난이도별 접근 전략
쉬움 (기본 탐색)
- 특징: 단순 연결 확인, 최단 거리 (가중치 없음)
- 전략: 기본 BFS/DFS 템플릿 사용
- 예시: 미로 탈출, 바이러스 확산, 연결 요소 개수
보통 (조건부 탐색)
- 특징: 특정 조건에서만 이동 가능, 상태 추가
- 전략: visited를 확장 (좌표, 방향, 키 등 상태 추가)
- 예시: 벽 부수기, 열쇠와 자물쇠, 말이 되고픈 원숭이
# 상태를 튜플로 관리
visited = set()
queue = deque([(x, y, broken_wall_count)]) # (좌표, 벽 부순 횟수)
어려움 (최적화 + 복합)
- 특징: 여러 알고리즘 조합, 최적화 필요
- 전략: BFS + DP, BFS + 이분 탐색, 양방향 BFS
- 예시: 숨바꼭질 3, 벽 부수고 이동하기 4, 이분 그래프
# 양방향 BFS (중간에서 만나기)
def bidirectional_bfs(graph, start, target):
if start == target:
return 0
# 양쪽에서 동시에 탐색
visited_from_start = {start: 0}
visited_from_target = {target: 0}
queue_start = deque([start])
queue_target = deque([target])
depth = 0
while queue_start or queue_target:
# start 쪽 탐색
if queue_start:
for _ in range(len(queue_start)):
node = queue_start.popleft()
# target 쪽에서 이미 방문했으면 만남
if node in visited_from_target:
return visited_from_start[node] + visited_from_target[node]
for neighbor in graph[node]:
if neighbor not in visited_from_start:
visited_from_start[neighbor] = visited_from_start[node] + 1
queue_start.append(neighbor)
# target 쪽 탐색 (동일 로직)
# ...
return -1
응용 팁
1. 최단 경로 + 경로 복원
def bfs_with_path(graph, start, target):
"""최단 경로와 함께 실제 경로도 반환"""
visited = {start}
queue = deque([(start, [start])]) # (노드, 경로)
while queue:
node, path = queue.popleft()
if node == target:
return path # 경로 반환
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
2. 가중치 있는 그래프는 다익스트라
주의: BFS는 가중치가 모두 같을 때만 최단 경로를 보장합니다. 가중치가 다르면 다익스트라(Dijkstra) 알고리즘을 사용해야 합니다.
3. 메모이제이션으로 최적화
# DFS + 메모이제이션 = DP
memo = {}
def dfs_with_memo(node, visited):
if node in memo:
return memo[node]
# 계산 로직
result = compute(node)
memo[node] = result
return result
4. 백트래킹과 결합
def dfs_backtracking(graph, node, path, all_paths):
"""모든 경로 탐색 + 백트래킹"""
path.append(node)
if is_target(node):
all_paths.append(path.copy()) # 복사 필수!
else:
for neighbor in graph[node]:
if neighbor not in path: # 사이클 방지
dfs_backtracking(graph, neighbor, path, all_paths)
path.pop() # 백트래킹 (상태 복원)
코딩 테스트 체크리스트
탐색 전:
– [ ] 방향 그래프인가? 무방향 그래프인가?
– [ ] 가중치가 있는가? (있으면 BFS 불가)
– [ ] 사이클이 있을 수 있는가?
– [ ] 그래프가 비어있거나 노드가 1개인 경우는?
구현 중:
– [ ] 방문 체크를 올바른 시점에 하는가?
– [ ] 2D 그리드는 범위 체크를 했는가?
– [ ] 큐/스택을 올바르게 사용하는가?
– [ ] 무방향 그래프는 양방향 간선을 추가했는가?
제출 전:
– [ ] 시간 복잡도가 제한 내인가? ( 확인)
– [ ] 엣지 케이스 (빈 그래프, 도달 불가능, 시작=끝)를 처리했는가?
– [ ] 메모리 제한을 초과하지 않는가?
마무리
BFS와 DFS는 그래프 탐색의 핵심 알고리즘입니다. 이 글에서 다룬 내용을 정리하면:
핵심 원리:
– BFS: 큐를 사용해 가까운 노드부터 탐색 → 최단 경로 보장
– DFS: 스택(재귀)을 사용해 깊이 우선 탐색 → 모든 경로 탐색
시간 복잡도:
– 둘 다 (모든 노드와 간선을 한 번씩 방문)
선택 기준:
– 최단 경로 필요 → BFS
– 모든 경로/백트래킹 필요 → DFS
– 메모리 제한 → DFS (재귀 스택이 큐보다 작음)
실전 팁:
1. 방문 체크는 큐/스택에 넣을 때 (BFS 중복 방지)
2. 2D 그리드는 범위 체크 먼저
3. 무방향 그래프는 양방향 간선 추가
4. 상태가 복잡하면 튜플로 visited 확장
5. 가중치 있으면 다익스트라 사용
이제 다양한 문제를 풀어보며 패턴을 익히세요. BFS/DFS는 연습할수록 빠르게 구현할 수 있습니다!
Did you find this helpful?
☕ Buy me a coffee
Leave a Reply