그래프를 탐색하는 대표적인 방법인 BFS와 DFS를 다룹니다.
BFS(Breadth-First Search)는 가까운 노드부터 탐색하고, DFS(Depth-First Search)는 한 방향으로 최대한 깊게 탐색합니다.
두 알고리즘은 그래프뿐 아니라 2차원 격자, 연결 요소, 경로 탐색 문제에서도 자주 사용됩니다.
1. 그래프란?
그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조입니다.
노드는 각각의 대상을, 간선은 대상 사이의 연결 관계를 나타냅니다.
예를 들어 사람을 노드, 친구 관계를 간선으로 표현할 수 있습니다.
1 - 2
| |
3 - 4- 그래프는 간선에 방향이 있는지에 따라 방향 그래프와 무방향 그래프로 구분할 수 있습니다.
2. 인접 리스트
Python에서는 그래프를 인접 리스트 형태로 표현하는 경우가 많습니다.
각 노드에 연결된 노드들을 리스트로 저장합니다.
graph = {
1: [2, 3],
2: [1, 4],
3: [1, 4],
4: [2, 3]
}
노드 번호가 연속된 정수라면 리스트로 표현할 수도 있습니다.
graph = [
[],
[2, 3],
[1, 4],
[1, 4],
[2, 3]
]
무방향 그래프에서는 두 방향의 연결을 모두 추가해야 합니다.
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)3. 방문 처리
그래프에는 같은 노드로 돌아오는 경로가 있을 수 있습니다.
방문 여부를 기록하지 않으면 같은 노드를 계속 탐색해 무한 반복이 발생할 수 있습니다.
visited = [False] * (N + 1)
노드에 방문할 때 값을 True로 변경합니다.
visited[node] = True- 방문 처리는 노드를 큐나 스택에 넣는 시점에 하는 것이 안전합니다.
4. BFS
BFS는 시작 노드에서 가까운 노드부터 차례대로 탐색합니다.
먼저 들어온 노드를 먼저 꺼내야 하므로 큐를 사용합니다.
Python에서는 collections.deque를 이용해 큐를 구현합니다.
from collections import deque
def bfs(graph, start):
visited = [False] * len(graph)
queue = deque([start])
visited[start] = True
while queue:
current = queue.popleft()
print(current)
for next_node in graph[current]:
if not visited[next_node]:
visited[next_node] = True
queue.append(next_node)
BFS의 동작 순서는 다음과 같습니다.
- 시작 노드를 큐에 넣고 방문 처리합니다.
- 큐의 앞에서 노드를 꺼냅니다.
- 현재 노드와 연결된 미방문 노드를 큐에 넣습니다.
- 큐가 빌 때까지 반복합니다.
5. BFS와 최단 거리
모든 간선의 비용이 같을 때 BFS로 시작점에서 각 노드까지의 최단 거리를 구할 수 있습니다.
from collections import deque
def bfs_distance(graph, start):
distance = [-1] * len(graph)
queue = deque([start])
distance[start] = 0
while queue:
current = queue.popleft()
for next_node in graph[current]:
if (distance[next_node] == -1):
distance[next_node] = distance[current] + 1
queue.append(next_node)
return distance- 처음 방문했을 때의 거리가 최단 거리입니다.
- 방문하지 않은 노드를 -1로 표시하면 방문 여부와 거리를 하나의 리스트로 관리할 수 있습니다.
6. DFS
DFS는 한 방향으로 갈 수 있는 만큼 깊게 탐색한 뒤, 더 이상 갈 수 없으면 이전 위치로 돌아갑니다.
재귀 함수 또는 스택으로 구현할 수 있습니다.
재귀를 이용한 DFS
def dfs(graph, current, visited):
visited[current] = True
print(current)
for next_node in graph[current]:
if not visited[next_node]:
dfs(graph, next_node, visited)
호출 방법은 다음과 같습니다.
visited = [False] * len(graph)
dfs(graph, 1, visited)- 재귀 호출이 함수의 실행 상태를 저장하므로 별도의 스택을 직접 만들지 않아도 됩니다.
스택을 이용한 DFS
def dfs(graph, start):
visited = [False] * len(graph)
stack = [start]
while stack:
current = stack.pop()
if visited[current]:
continue
visited[current] = True
print(current)
for next_node in reversed(graph[current]):
if not visited[next_node]:
stack.append(next_node)- 스택은 마지막에 넣은 값을 먼저 꺼내므로 탐색 순서를 맞추려면 이웃 노드를 넣는 순서를 확인해야 합니다.
7. BFS와 DFS 비교
| 구분 | BFS | DFS |
|---|---|---|
| 탐색 방법 | 가까운 노드부터 탐색 | 한 방향으로 깊게 탐색 |
| 주요 자료구조 | 큐 | 재귀 또는 스택 |
| 최단 거리 | 간선 비용이 같을 때 적합 | 최단 거리 보장 안 됨 |
| 자주 쓰이는 문제 | 최소 이동 횟수, 거리 | 연결 요소, 경로 존재, 백트래킹 |
- 그래프의 모든 노드와 간선을 한 번씩 확인한다면 두 알고리즘의 시간복잡도는 모두 O(V + E)입니다.
- V는 노드의 수, E는 간선의 수입니다.
8. 2차원 격자 탐색
격자의 각 칸을 노드로, 상하좌우 이동을 간선으로 생각할 수 있습니다.
방향 배열을 사용하면 네 방향을 반복문으로 처리할 수 있습니다.
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(4):
next_row = row + dr[i]
next_col = col + dc[i]
격자 밖으로 이동하지 않는지 확인해야 합니다.
if (0 <= next_row < rows and 0 <= next_col < cols):
print(next_row, next_col)9. 미로 최단 거리
1은 이동 가능한 칸, 0은 이동할 수 없는 칸이라고 가정하겠습니다.
모든 이동의 비용이 1이므로 BFS를 이용해 최단 거리를 구할 수 있습니다.
from collections import deque
def shortest_path(board):
rows = len(board)
cols = len(board[0])
distance = [[-1] * cols for _ in range(rows)]
distance[0][0] = 0
queue = deque([(0, 0)])
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
while queue:
row, col = queue.popleft()
for i in range(4):
next_row = row + dr[i]
next_col = col + dc[i]
if not (0 <= next_row < rows and 0 <= next_col < cols):
continue
if (board[next_row][next_col] == 0):
continue
if (distance[next_row][next_col] != -1):
continue
distance[next_row][next_col] = distance[row][col] + 1
queue.append((next_row, next_col))
return distance[rows - 1][cols - 1]- 각 칸은 최대 한 번 방문하므로 시간복잡도는 O(rows × cols)입니다.
10. 연결 요소 찾기
서로 연결된 노드들의 묶음을 연결 요소라고 합니다.
방문하지 않은 노드에서 DFS 또는 BFS를 시작할 때마다 새로운 연결 요소를 발견한 것입니다.
def dfs(graph, current, visited):
visited[current] = True
for next_node in graph[current]:
if not visited[next_node]:
dfs(graph, next_node, visited)
def count_components(graph):
visited = [False] * len(graph)
count = 0
for node in range(1, len(graph)):
if not visited[node]:
dfs(graph, node, visited)
count += 1
return count- 그래프가 여러 개의 분리된 영역으로 구성되어 있을 때 사용할 수 있습니다.
11. 탐색 순서
문제에서 방문 순서를 요구한다면 인접 리스트를 정렬해야 할 수 있습니다.
for nodes in graph:
nodes.sort()BFS는 큐에 넣은 순서, DFS는 재귀 호출 또는 스택에 넣는 순서에 따라 결과가 달라집니다.
단순히 모든 노드의 방문 여부만 중요하다면 정렬이 필요하지 않을 수 있습니다.
12. 자주 하는 실수/주의점
- 방문 배열을 만들지 않으면 같은 노드를 반복해서 탐색할 수 있습니다.
- BFS에서 리스트의
pop(0)대신deque.popleft()를 사용합니다. - 큐에 넣을 때 방문 처리하지 않으면 같은 노드가 여러 번 들어갈 수 있습니다.
- 무방향 그래프는
a → b,b → a를 모두 추가해야 합니다. - 격자 탐색에서는 범위 확인을 먼저 해야 합니다.
- 재귀 DFS는 그래프가 깊을 때 Python의 재귀 깊이 제한에 걸릴 수 있습니다.
- DFS는 일반적으로 최단 거리를 보장하지 않습니다.
- 문제에서 요구하는 방문 순서가 있는지 확인해야 합니다.
13. 종합 요약
- 그래프는 노드와 간선으로 구성
- 인접 리스트로 각 노드의 연결 관계 저장
- BFS는 큐를 사용하여 가까운 노드부터 탐색
- DFS는 재귀 또는 스택을 사용하여 깊게 탐색
- 간선 비용이 모두 같을 때 BFS로 최단 거리 탐색 가능
- 방문 배열로 중복 탐색 방지
- 2차원 격자도 그래프로 생각할 수 있음
- BFS와 DFS의 시간복잡도는 인접 리스트 기준
O(V + E)
'GDGoC > Python' 카테고리의 다른 글
| [Python] Algorithm #07: 최단 경로와 그리디 (1) | 2026.08.12 |
|---|---|
| [Python] Algorithm #05: 동적 계획법 (Dynamic Programming) (0) | 2026.08.12 |
| [Python] Basic #07: 시간복잡도 (0) | 2026.08.12 |
| [Python] Basic #06: 자료구조 (0) | 2026.08.12 |
| [Python] Basic #05: 반복문 심화 (0) | 2026.08.12 |