Quick Comparison
방향·무방향, 가중치 여부, 중복 간선 허용 여부를 먼저 정하고 표현을 고릅니다. BFS·DFS는 대부분 인접 리스트, 모든 정점 쌍을 갱신하는 Floyd-Warshall은 행렬, 간선을 비용순으로 처리하는 Kruskal은 간선 리스트가 자연스럽습니다.
| 표현 | 공간 | 간선 존재 확인 | 이웃 순회 | 적합한 경우 |
|---|---|---|---|---|
| 인접 리스트 | O(V + E) | O(deg) | O(deg) | 간선이 적은 그래프 |
| 인접 행렬 | O(V²) | O(1) | O(V) | 정점 수가 작고 간선 확인이 많음 |
| 간선 리스트 | O(E) | O(E) | O(E) | 정렬, union-find |
구조
그래프는 정점(vertex)과 간선(edge)으로 이루어진 구조입니다. 문제에서 도시, 사람, 컴퓨터, 칸, 상태가 나오면 정점 후보이고, 연결, 이동, 관계, 변환이 나오면 간선 후보입니다.
V = 정점 수
E = 간선 수그래프는 방향이 있을 수도 있고, 없을 수도 있습니다. 비용이 붙으면 가중치 그래프입니다. from -> to는 방향 간선 하나만 넣고, 무방향 간선은 from -> to와 to -> from을 모두 넣습니다. 같은 두 정점 사이의 여러 간선을 허용하는지도 입력 조건에서 확인해야 합니다.
static List<(int To, long Cost)>[] BuildUndirectedWeightedGraph(
int vertexCount,
IEnumerable<(int From, int To, long Cost)> edges)
{
var graph = new List<(int To, long Cost)>[vertexCount];
for (int vertex = 0; vertex < vertexCount; vertex++) graph[vertex] = new();
foreach ((int from, int to, long cost) in edges)
{
graph[from].Add((to, cost));
graph[to].Add((from, cost));
}
return graph;
}인접 리스트
인접 리스트는 각 정점마다 연결된 이웃 목록을 저장합니다. 대부분의 코테 그래프 문제에서 기본 선택입니다. 특히 E가 V²보다 훨씬 작으면 메모리를 크게 줄일 수 있습니다. List<T>로 저장한 인접 리스트는 특정 간선 존재를 확인하려면 그 정점의 목록을 훑어야 합니다. 이 질의가 매우 많다면 HashSet<int> 또는 행렬을 선택하지만, HashSet은 메모리와 상수 비용이 커집니다.
인접 행렬
인접 행렬은 matrix[a, b]에 a에서 b로 가는 간선이 있는지 저장합니다. 간선 존재 확인은 빠르지만, 정점 수가 크면 메모리 O(V²)이 부담됩니다. 가중치 행렬에서는 0을 간선 없음 표식으로 쓰면 비용 0 간선을 잃으므로 INF 같은 별도 표식이 필요합니다.
static long[,] BuildUndirectedCostMatrix(
int vertexCount,
IEnumerable<(int From, int To, long Cost)> edges)
{
const long INF = long.MaxValue / 4;
var cost = new long[vertexCount, vertexCount];
for (int from = 0; from < vertexCount; from++)
{
for (int to = 0; to < vertexCount; to++)
{
cost[from, to] = from == to ? 0 : INF;
}
}
foreach ((int from, int to, long edgeCost) in edges)
{
if (edgeCost <= -INF || edgeCost >= INF) throw new ArgumentOutOfRangeException(nameof(edges));
cost[from, to] = Math.Min(cost[from, to], edgeCost);
cost[to, from] = Math.Min(cost[to, from], edgeCost);
}
return cost;
}선택 기준
| 조건 | 표현 |
|---|---|
V가 크고 E가 작음 | 인접 리스트 |
| 모든 간선 존재 여부를 자주 확인 | 인접 행렬 |
| 간선을 비용순으로 정렬 | 간선 리스트 |
| BFS, DFS 기본 탐색 | 인접 리스트 |
| 플로이드-워셜 | 인접 행렬 |
| 크루스칼 MST | 간선 리스트 |
정점 번호가 1부터 시작하는 문제는 배열 크기를 n + 1로 잡거나 입력을 0-based로 바꿔야 합니다. 두 방식을 섞으면 off-by-one 오류가 자주 납니다. 행렬은 long[V, V]만으로도 약 8 × V² bytes를 쓰므로, V가 커지면 간선 수가 적어도 메모리 제한을 먼저 넘을 수 있습니다.
주의할 점
무방향 그래프는 간선을 양쪽에 넣어야 합니다. a -> b만 넣으면 탐색이 한 방향으로만 진행됩니다.
반대로 방향 그래프에서 양쪽에 넣으면 존재하지 않는 경로를 만들어 오답이 됩니다. 입력 설명에서 “양방향”, “단방향”, “서로 이동 가능” 같은 표현을 먼저 확인하세요.
참고 링크
1 sources