thenullpage.com
1. 관계 자체를 저장해야 할 때
트리는 부모에서 자식으로 내려가기만 합니다. 그런데 현실의 연결은 그렇게 한 방향으로만 흐르지 않습니다. 지하철 노선도는 역에서 역으로 이어지고 되돌아올 수도 있으며 여러 갈래로 갈라집니다. 친구 관계도 마찬가지입니다. 이런 연결을 그대로 담는 구조가 그래프(graph)입니다.
점을 정점(vertex), 잇는 선을 간선(edge)이라고 부릅니다. 그래프를 다루는 일은 결국 어떤 정점이 어떤 정점과 이어져 있는지를 코드로 적어 두고 그것을 빠르게 물어보는 일입니다. 적는 방법은 크게 두 가지이고, 어느 쪽을 골랐느냐에 따라 싸게 답할 수 있는 질문이 달라집니다.
2. 표로 적는 인접 행렬
정점에 0번부터 번호를 붙이고 정사각형 표를 만듭니다. i행 j열이 1이면 i에서 j로 가는 간선이 있다는 뜻입니다.
n = 5
matrix = [[0] * n for _ in range(n)]
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
for a, b in edges:
matrix[a][b] = 1
matrix[b][a] = 1
for row in matrix:
print(row)
[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 0]
[0, 1, 1, 0, 1]
[0, 0, 0, 1, 0]
양쪽 칸에 모두 1을 넣은 것은 어느 방향으로도 오갈 수 있는 무방향 그래프이기 때문입니다. 0과 3이 이어져 있느냐는 질문에는 matrix[0][3]을 읽으면 끝이라 O(1)입니다. 대신 표 크기는 정점 수의 제곱이라 간선이 다섯 개뿐인데도 칸을 스물다섯 개 씁니다. 표를 만들 때 [[0] * n] * n 이라고 쓰면 같은 행을 다섯 번 가리키게 되어 한 칸만 바꿔도 모든 행이 같이 바뀝니다. 표의 대각선은 자기 자신으로 가는 간선을 뜻하는데, 보통 그런 간선은 없으므로 전부 0으로 남습니다.
3. 이웃만 적어 두는 인접 리스트
표 대신 정점마다 자기와 이어진 정점만 모아 두는 방식입니다. 간선 목록을 그대로 들고 있다가 필요할 때마다 훑는 방법도 있지만, 이웃 하나를 물을 때마다 간선 전체를 확인해야 해서 정점이 조금만 늘어도 감당이 되지 않습니다.
from collections import defaultdict
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
for v in range(n):
print(v, graph[v])
0 [1, 2]
1 [0, 3]
2 [0, 3]
3 [1, 2, 4]
4 [3]
적어 둔 칸 수가 간선 수에 비례하므로 메모리는 O(V+E)입니다. 0의 이웃을 전부 훑는 일도 두 칸만 읽으면 끝납니다. 인접 행렬이었다면 0번 행 다섯 칸을 전부 확인해서 1이 적힌 자리를 골라내야 합니다. 반대로 0과 3이 이어졌느냐는 질문에는 graph[0]을 처음부터 훑어야 해서 이웃 수만큼 비용이 듭니다. 행렬이 싸게 답하던 질문을 리스트는 비싸게 답하고, 그 반대도 그렇습니다.
4. 어느 쪽을 고를지
둘 중 하나를 고르는 기준은 간선이 얼마나 촘촘한가입니다. 정점 천 개에 간선 삼천 개인 그래프로 칸 수를 재 보겠습니다.
V = 1000
E = 3000
print(V * V)
print(2 * E)
1000000
6000
행렬은 백만 칸이고 리스트는 육천 칸입니다. 정점이 십만 개로 늘면 행렬은 백억 칸이라 메모리가 감당되지 않습니다. 실제 문제의 그래프는 이렇게 간선이 듬성듬성한 경우가 많아서 대개 인접 리스트를 씁니다. 행렬이 나은 경우는 정점이 적으면서 거의 모든 쌍이 이어져 있거나, 두 정점이 이어졌는지를 아주 자주 물어야 할 때입니다.
5. 방향과 가중치 붙이기
일방통행이면 한쪽에만 넣습니다. 거리나 비용 같은 값이 있으면 정점 번호와 함께 튜플로 넣으면 됩니다.
road = defaultdict(list)
for a, b, cost in [(0, 1, 5), (1, 2, 3), (0, 2, 9)]:
road[a].append((b, cost))
print(road[0])
print(road[1])
print(road[2])
[(1, 5), (2, 9)]
[(2, 3)]
[]
한쪽에만 넣었으니 0에서 1로는 갈 수 있어도 1에서 0으로는 갈 수 없습니다. 가중치가 있으면서 양방향인 그래프라면 road[a]에 (b, cost)를, road[b]에 (a, cost)를 각각 넣어 주면 됩니다. road[2]가 빈 리스트로 나온 것은 defaultdict가 없는 키를 물으면 빈 리스트를 만들어 넣어 주기 때문입니다. 읽기만 했는데 키가 늘어나는 셈이라 나중에 len(road)를 재면 값이 달라져 있습니다. 이 점이 곤란하면 처음부터 [[] for _ in range(n)] 으로 만들어 두는 편이 낫습니다.
6. 격자도 그래프입니다
지도나 미로처럼 생긴 2차원 배열도 그래프입니다. 다만 간선을 따로 저장하지 않고 좌표 계산으로 이웃을 구합니다. 이웃 목록을 미리 만들어 둘 필요가 없으니 메모리도 판 크기만큼만 듭니다.
grid = [
[0, 0, 1],
[1, 0, 0],
[0, 0, 0],
]
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
r, c = 1, 1
for dr, dc in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < 3 and 0 <= nc < 3 and grid[nr][nc] == 0:
print(nr, nc)
0 1
2 1
1 2
가운데 칸에서 위 아래 왼쪽 오른쪽으로 한 칸씩 옮겨 보고, 판 안쪽이면서 막히지 않은 칸만 남겼습니다. 왼쪽 칸은 값이 1이라 빠졌습니다. 여기서 범위 검사를 빼먹으면 안 됩니다. 파이썬에서 grid[-1]은 오류가 아니라 마지막 행이라서, 판 밖으로 나간 좌표가 반대편 끝 칸을 이웃으로 데려옵니다.
7. 자주 걸리는 곳
무방향 그래프인데 한쪽만 넣어서 절반이 끊기는 실수가 가장 흔합니다. 반대로 같은 간선이 두 번 들어오는 경우도 있습니다.
dup = defaultdict(list)
for a, b in [(0, 1), (1, 0), (0, 1)]:
dup[a].append(b)
dup[b].append(a)
print(dup[0])
print(dup[1])
[1, 1, 1]
[0, 0, 0]
입력이 같은 간선을 세 번 적은 것인데 코드가 그대로 받아 이웃이 세 개씩 들어갔습니다. 이웃을 훑는 코드는 같은 정점을 세 번 보게 되고, 방문 표시를 하지 않으면 같은 일을 반복합니다. 중복이 곤란하면 리스트 대신 set에 담습니다. 자기 자신으로 가는 간선도 걸러지지 않고 그대로 들어가니, 그런 간선이 의미 없는 문제라면 a와 b가 같을 때 건너뛰어야 합니다.
8. 챙길 것
그래프는 관계를 적어 두는 구조이고, 적는 방법에 따라 싸게 답할 수 있는 질문이 달라집니다.
기억할 것은 세 가지입니다. 인접 행렬은 메모리를 O(V^2) 쓰는 대신 두 정점의 연결 확인이 O(1)이라는 것, 인접 리스트는 메모리가 O(V+E)이고 이웃 순회가 빨라서 간선이 듬성듬성한 대부분의 경우에 기본이 된다는 것, 그리고 무방향이면 양쪽에 모두 넣어야 하고 격자는 간선을 저장하지 않고 좌표 계산으로 이웃을 구한다는 것입니다.