핵심 정리
| 표현 | 공간 | 간선 존재 확인 | 이웃 순회 | 적합한 경우 |
|---|---|---|---|---|
| 인접 리스트 | O(V + E) | O(deg) | O(deg) | 간선이 적은 그래프 |
| 인접 행렬 | O(V²) | O(1) | O(V) | 정점 수가 작고 간선 확인이 많음 |
| 간선 리스트 | O(E) | O(E) | O(E) | 정렬, union-find |
csharp
var graph = new List<int>[n];
for (int i = 0; i < n; i++) graph[i] = new List<int>();
graph[a].Add(b);
graph[b].Add(a); // 무방향 그래프구조
그래프는 정점(vertex)과 간선(edge)으로 이루어진 구조입니다. 문제에서 도시, 사람, 컴퓨터, 칸, 상태가 나오면 정점 후보이고, 연결, 이동, 관계, 변환이 나오면 간선 후보입니다.
text
V = 정점 수
E = 간선 수그래프는 방향이 있을 수도 있고, 없을 수도 있습니다. 비용이 붙으면 가중치 그래프입니다.
csharp
// 가중치 그래프 인접 리스트
var weighted = new List<(int To, int Cost)>[n];
for (int i = 0; i < n; i++) weighted[i] = new();
weighted[from].Add((to, cost));인접 리스트
인접 리스트는 각 정점마다 연결된 이웃 목록을 저장합니다. 대부분의 코테 그래프 문제에서 기본 선택입니다. 특히 E가 V²보다 훨씬 작으면 메모리를 크게 줄일 수 있습니다.
인접 행렬
인접 행렬은 matrix[a, b]에 a에서 b로 가는 간선이 있는지 저장합니다. 간선 존재 확인은 빠르지만, 정점 수가 크면 메모리 O(V²)이 부담됩니다.
csharp
bool[,] connected = new bool[n, n];
connected[a, b] = true;
connected[b, a] = true;선택 기준
| 조건 | 표현 |
|---|---|
V가 크고 E가 작음 | 인접 리스트 |
| 모든 간선 존재 여부를 자주 확인 | 인접 행렬 |
| 간선을 비용순으로 정렬 | 간선 리스트 |
| BFS, DFS 기본 탐색 | 인접 리스트 |
| 플로이드-워셜 | 인접 행렬 |
| 크루스칼 MST | 간선 리스트 |
정점 번호가 1부터 시작하는 문제는 배열 크기를 n + 1로 잡거나 입력을 0-based로 바꿔야 합니다. 두 방식을 섞으면 off-by-one 오류가 자주 납니다.
주의할 점
무방향 그래프는 간선을 양쪽에 넣어야 합니다. a -> b만 넣으면 탐색이 한 방향으로만 진행됩니다.
반대로 방향 그래프에서 양쪽에 넣으면 존재하지 않는 경로를 만들어 오답이 됩니다. 입력 설명에서 “양방향”, “단방향”, “서로 이동 가능” 같은 표현을 먼저 확인하세요.