그래프 입력은 BFS나 DFS를 시작하기 전에 먼저 정해야 하는 구조입니다. 같은 간선 목록을 받아도 인접 리스트로 만들지, 인접 행렬로 만들지에 따라 코드와 메모리 사용량이 달라집니다.
핵심은 문제에서 자주 하는 연산이 무엇인지 먼저 보는 것입니다. 모든 노드의 이웃을 훑는지, 두 노드가 연결됐는지만 빠르게 확인하는지에 따라 좋은 표현이 달라집니다.
그래프 입력은 왜 먼저 어렵게 느껴질까
배열 문제는 입력을 그대로 리스트에 담으면 시작할 수 있습니다. 하지만 그래프 문제는 입력이 보통 간선 목록으로 들어옵니다. 이 간선 목록을 탐색하기 좋은 구조로 바꿔야 BFS, DFS, 최단거리 알고리즘을 쓸 수 있습니다.
예를 들어 정점 1과 2가 연결되어 있다는 입력 한 줄은 코드 안에서 여러 형태가 될 수 있습니다. graph[1]에 2를 넣을 수도 있고, matrix[1][2]를 True로 바꿀 수도 있습니다.
인접 리스트는 언제 자연스러울까
인접 리스트는 각 정점마다 연결된 정점 목록을 저장합니다. BFS나 DFS처럼 현재 정점에서 갈 수 있는 이웃을 순서대로 훑는 문제에 잘 맞습니다.
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) # 무방향 그래프라면 양쪽에 넣는다간선 수가 정점 수에 비해 적은 그래프라면 인접 리스트가 보통 메모리에 유리합니다. 실제 연결된 간선만 저장하기 때문입니다.
인접 행렬은 언제 쓸 만할까
인접 행렬은 n x n 표를 만들고, a와 b가 연결되어 있으면 matrix[a][b]를 표시합니다. 두 정점이 직접 연결되어 있는지 자주 확인해야 하는 문제에서는 코드가 단순해집니다.
n, m = map(int, input().split())
connected = [[False] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
connected[a][b] = True
connected[b][a] = True다만 정점이 많아지면 n x n 메모리가 바로 부담이 됩니다. 정점이 100,000개인 문제에서 인접 행렬을 만들면 탐색 전에 메모리부터 터질 수 있습니다.
시간복잡도와 메모리 차이
- 인접 리스트 메모리: 보통 O(V + E)
- 인접 행렬 메모리: 보통 O(V^2)
- 어떤 정점의 모든 이웃 순회: 인접 리스트가 실제 이웃만 돈다
- 두 정점의 연결 여부 확인: 인접 행렬은 O(1)에 가깝게 확인한다
방향 그래프와 무방향 그래프에서 달라지는 점
무방향 그래프라면 a-b 간선 하나를 입력받았을 때 graph[a]에도 b를 넣고 graph[b]에도 a를 넣습니다. 방향 그래프라면 a에서 b로 가는 간선만 넣어야 합니다.
# 방향 그래프
graph[a].append(b)
# 무방향 그래프
graph[a].append(b)
graph[b].append(a)가중치가 있으면 어떻게 담을까
최단거리 문제처럼 간선에 비용이 있으면 이웃 정점만 저장하면 부족합니다. 인접 리스트에는 보통 `(다음 정점, 비용)` 형태의 튜플을 넣습니다.
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, cost = map(int, input().split())
graph[a].append((b, cost))입력 예제로 직접 비교하기
4 4
1 2
1 3
2 4
3 4이 입력을 인접 리스트로 만들면 1번 정점의 이웃은 [2, 3]입니다. 인접 행렬로 만들면 connected[1][2]와 connected[1][3]이 True가 됩니다. 같은 정보지만 탐색 방식이 달라집니다.
실전 선택 기준
- BFS/DFS로 이웃을 계속 훑으면 인접 리스트를 먼저 생각한다
- 정점 수가 크고 간선 수가 상대적으로 적으면 인접 리스트를 쓴다
- 두 정점 연결 여부를 매우 자주 묻고 정점 수가 작으면 인접 행렬을 검토한다
- 가중치가 있으면 리스트 원소에 비용을 함께 저장한다
- 방향/무방향 조건을 입력 처리 단계에서 확실히 반영한다
자주 하는 실수
- 무방향 그래프인데 한쪽 방향만 넣는다
- 1번부터 시작하는 정점인데 배열을 n개만 만든다
- 정점 수가 큰데 인접 행렬을 만든다
- 가중치가 있는데 정점 번호만 저장한다
- BFS visited 처리를 입력 구조 문제와 섞어서 디버깅한다
정리
그래프 입력은 알고리즘의 시작점입니다. 인접 리스트와 인접 행렬은 어느 쪽이 항상 좋은 구조가 아니라, 문제에서 자주 하는 연산에 맞춰 고르는 표현입니다.
BFS 구현 흐름은 CP-Algorithms BFS 문서를 기준으로 확인할 수 있습니다. 방문 처리 기준은 BFS visited 체크 글과 함께 보면 좋습니다.
