그래프 탐색은 정점과 간선으로 이루어진 구조에서 시작 정점부터 갈 수 있는 모든 정점을 빠짐없이, 한 번씩만 방문하는 방법입니다. 지도, 소셜 네트워크, 작업 의존 관계, 미로처럼 "무엇이 무엇과 이어져 있는가"로 표현되는 문제는 대부분 그래프 탐색으로 풀 수 있습니다. 이 장에서는 기본 용어와 그래프를 코드로 담는 방법, 그리고 두 가지 대표 탐색인 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)의 직관을 정리합니다.
기본 용어
보통 정점 수를 V, 간선 수를 E로 씁니다. 그래프 알고리즘의 복잡도는 거의 항상 이 두 값으로 표현합니다.
그래프를 코드로 담는 방법
가장 많이 쓰는 표현은 인접 리스트입니다. 정점마다 이웃 목록을 저장하므로 메모리가 O(V + E)이고, 한 정점의 이웃을 차례로 볼 때 실제 이웃 수만큼만 시간이 듭니다.
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 무방향이면 반대쪽도 추가
print(graph[2]) # [0, 3, 4]
인접 행렬은 V x V 크기의 2차원 표에 간선 유무를 기록합니다. 두 정점이 이어졌는지 O(1)에 확인할 수 있지만 메모리가 O(V^2)이라 정점이 많고 간선이 적은 희소 그래프에는 맞지 않습니다.
n = 6
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = matrix[v][u] = 1
print(matrix[2][4] == 1) # True: 2와 4는 이웃
간선 목록(edges 그 자체)도 하나의 표현입니다. 크루스칼 알고리즘처럼 간선을 정렬해서 다루는 경우에 편하지만, 이웃을 찾으려면 전체를 훑어야 하므로 탐색에는 보통 인접 리스트로 바꿔서 씁니다.
방향과 번호 다루기
방향 그래프라면 u→v 한쪽만 추가합니다. 정점이 문자열(도시 이름, 모듈 이름)이라면 사전을 쓰거나, 이름마다 0부터 번호를 붙여 리스트 기반 인접 리스트로 바꾸면 더 빠르고 메모리도 적게 듭니다. 문제에서 정점 번호가 1부터 시작하면 리스트 크기를 n + 1로 잡거나 번호에서 1을 빼서 맞춰야 범위 오류가 나지 않습니다.
names = ["core", "ui", "app"]
index = {name: i for i, name in enumerate(names)}
adj = [[] for _ in names]
for before, after in [("core", "ui"), ("ui", "app")]:
adj[index[before]].append(index[after]) # 방향 간선만
print(adj) # [[1], [2], []]
격자도 그래프다
미로나 지도처럼 2차원 격자로 주어진 문제는 각 칸을 정점으로, 상하좌우로 이웃한 칸 사이를 간선으로 보면 됩니다. 이런 그래프는 인접 리스트를 따로 만들지 않고 이웃을 그때그때 계산하는 암시적 그래프로 다룹니다.
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbors(grid, r, c):
rows, cols = len(grid), len(grid[0])
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
yield nr, nc
BFS와 DFS의 직관
- BFS(너비 우선 탐색): 시작점에서 가까운 정점부터 한 겹씩 넓혀 갑니다. 큐(queue)를 씁니다. 간선 가중치가 모두 같은 그래프에서 최단 경로(간선 수가 가장 적은 경로)를 구합니다.
- DFS(깊이 우선 탐색): 한 방향으로 갈 수 있는 데까지 깊이 들어갔다가 막히면 되돌아옵니다. 재귀 호출이나 스택을 씁니다. 연결 요소, 사이클 탐지, 위상 정렬, 백트래킹의 뼈대가 됩니다.
두 방법 모두 방문 표시(visited)가 핵심입니다. 이미 본 정점을 다시 넣지 않아야 사이클이 있는 그래프에서도 끝나고, 전체 시간이 O(V + E)로 묶입니다.
언제 무엇을 쓰나
정리
그래프는 정점과 간선으로 관계를 표현하고, 탐색은 방문 표시를 남기며 이웃을 따라가는 일입니다. 대부분의 경우 인접 리스트가 기본 선택이고, 격자는 이웃을 계산하는 암시적 그래프로 다룹니다. 가까운 곳부터 넓히는 BFS는 가중치 없는 최단 거리에, 깊이 들어가는 DFS는 구조 분석(연결 요소, 사이클, 위상 정렬)에 주로 씁니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.