프림 알고리즘 (Prim), 위상정렬
1. 오늘의 학습 흐름
- 프림 알고리즘 개념 및 구현
- SWEA 1251 하나로 (MST 적용)
- 위상정렬
2. 프림 알고리즘이란
크루스칼과 마찬가지로 MST를 구하는 알고리즘이다. 접근 방식이 다르다.
크루스칼: 간선 중심 → 가중치 작은 간선부터 선택, 사이클 체크
프림: 정점 중심 → 현재 트리에서 가장 가까운 정점을 하나씩 추가다익스트라와 구조가 매우 유사하다. 차이는 다익스트라는 "출발점에서 해당 정점까지의 누적 거리"를 기준으로 선택하고, 프림은 "현재 트리에서 해당 정점까지의 간선 가중치"만 본다.
3. 프림 동작 방식
1. 임의의 시작 정점을 MST에 포함
2. MST에 포함된 정점들과 인접한 정점 중, 연결 간선 가중치가 가장 작은 정점 선택
3. 해당 정점을 MST에 추가
4. V-1개의 정점이 추가될 때까지 반복4. 프림 구현 - PriorityQueue 버전
static int[] minEdge; // 각 정점을 트리에 연결하는 최소 간선 가중치
static boolean[] inMST; // MST에 포함됐는지 여부
static int prim(int start) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
Arrays.fill(minEdge, Integer.MAX_VALUE);
minEdge[start] = 0;
pq.offer(new int[]{start, 0});
int totalCost = 0;
int count = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int v = cur[0], cost = cur[1];
if (inMST[v]) continue; // 이미 MST에 포함된 정점 skip
inMST[v] = true;
totalCost += cost;
if (++count == V) break;
for (int[] next : list[v]) {
int nv = next[0], nw = next[1];
if (!inMST[nv] && minEdge[nv] > nw) {
minEdge[nv] = nw;
pq.offer(new int[]{nv, nw});
}
}
}
return totalCost;
}다익스트라와 코드 구조가 거의 같다. 핵심 차이:
- 다익스트라:
dist[next] > dist[now] + nw→ 누적 거리 갱신 - 프림:
minEdge[nv] > nw→ 간선 가중치만 갱신 (누적 X)
5. 크루스칼 vs 프림 비교
| 크루스칼 | 프림 | |
|---|---|---|
| 접근 방식 | 간선 중심 | 정점 중심 |
| 핵심 자료구조 | Disjoint Set + 간선 정렬 | PriorityQueue + visited |
| 시간복잡도 | O(ElogE) | O(ElogV) |
| 유리한 경우 | 간선이 적은 희소 그래프 | 간선이 많은 밀집 그래프 |
| 사이클 처리 | union-find로 감지 | visited 배열로 방지 |
정점 수가 작고 간선이 많으면 프림, 간선이 적으면 크루스칼이 유리하다.
6. 프림 실제 코드 (MST2_Prim_PQ2)
무향 그래프에서 1번 정점을 시작으로 MST를 구하는 코드다.
static int prim(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0)); // 시작 정점, 비용 0
int totalWeight = 0;
int count = 0;
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (visited[cur.v]) continue; // 이미 MST 포함 → skip
visited[cur.v] = true;
totalWeight += cur.w;
if (++count == V) break; // 모든 정점 포함 시 종료
for (Node node : graph[cur.v]) {
if (!visited[node.v]) {
pq.offer(node); // 아직 MST 미포함 정점만 후보로
}
}
}
return totalWeight;
}다익스트라와 구조가 거의 동일하다. 차이를 한 줄로 정리하면:
다익스트라: pq.offer(new Node(nv, dist[now] + nw)) → 누적 거리 기준
프림: pq.offer(new Node(nv, nw)) → 간선 가중치 기준7. SWEA 1251 - 하나로
섬들을 해저 터널로 연결하는데 비용이 최소가 되게 하는 MST 문제다. 거리가 유클리드 거리의 제곱이라 double을 써야 한다.
크루스칼 버전 (224ms):
static class Edge implements Comparable<Edge> {
int from, to;
double cost;
public Edge(int st, int ed) {
this.from = st;
this.to = ed;
this.cost = distance(st, ed);
}
public double distance(int i, int j) {
return (Math.pow(Math.abs(ArrX[i] - ArrX[j]), 2)
+ Math.pow(Math.abs(ArrY[i] - ArrY[j]), 2)) * E;
}
}
// 모든 섬 쌍에 대한 간선 생성 후 크루스칼 적용
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
pq.add(new Edge(i, j));
}
}프림 버전:
static double getCost(int a, int b) {
long dx = ArrX[a] - ArrX[b];
long dy = ArrY[a] - ArrY[b];
return (dx * dx + dy * dy) * E; // Math.pow 대신 직접 곱셈으로 최적화
}
// 모든 섬이 연결 가능하므로 인접 리스트 없이 모든 정점에 대해 비용 계산
for (int i = 0; i < N; i++) {
if (!visited[i]) {
pq.offer(new Node(i, getCost(cur.v, i)));
}
}Math.pow() 대신 직접 곱셈(dx * dx)을 쓰면 더 빠르다. long으로 받아서 overflow도 방지한다.
결과는 Math.round()로 반올림 출력한다.
8. 위상 정렬 (Topological Sort)
DAG(사이클 없는 방향 그래프)에서 선행 관계를 만족하는 순서로 정점들을 나열하는 알고리즘이다. "선수 과목 이수 순서", "빌드 의존성 순서" 같은 문제에 쓰인다.
BFS 기반으로 구현한다. 진입 차수(In-Degree)가 핵심이다.
진입 차수(In-Degree): 해당 정점으로 들어오는 간선의 수
→ 진입 차수가 0인 정점은 선행 조건 없음 = 먼저 처리 가능동작 방식
0. 입력 받으면서 to 노드의 진입 차수 증가
1. 진입 차수가 0인 노드를 모두 큐에 넣기
2. 큐가 빌 때까지 반복:
2.1 큐에서 꺼내서 결과에 추가
2.2 해당 노드와 연결된 노드들의 진입 차수 -1
2.3 진입 차수가 0이 된 노드를 큐에 추가
3. 결과 리스트 크기 == N이면 위상 정렬 성공
아니면 사이클 존재 (cycle 출력)구현 코드
int[] inDegree = new int[N + 1];
ArrayList<Integer>[] list = new ArrayList[N + 1];
// 간선 입력
list[from].add(to);
inDegree[to]++; // to의 진입 차수 증가
// 1. 진입 차수 0인 노드 큐에 넣기
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
// 2. BFS
while (!queue.isEmpty()) {
int cur = queue.poll();
result.add(cur);
for (int next : list[cur]) {
if (--inDegree[next] == 0) { // 진입 차수가 0이 되면 큐에 추가
queue.offer(next);
}
}
}
// 3. 사이클 감지
if (result.size() == N) { /* 출력 */ }
else System.out.println("cycle");BOJ 2252 - 줄 세우기
위상 정렬을 그대로 적용하는 문제다. "A가 B 앞에 선다"는 입력을 방향 간선으로 표현하고 위상 정렬하면 전체 줄 순서가 나온다.
// A → B 간선: A가 B보다 앞에 서야 함
list[from].add(to);
inDegree[to]++;9. 크루스칼 vs 프림 vs 다익스트라 최종 정리
| 크루스칼 | 프림 | 다익스트라 | |
|---|---|---|---|
| 목적 | MST | MST | 최단 거리 |
| 접근 | 간선 중심 | 정점 중심 | 정점 중심 |
| 갱신 기준 | 간선 가중치 | 간선 가중치 | 누적 거리 |
| 자료구조 | Disjoint Set | PQ + visited | PQ + visited |
| 시간복잡도 | O(ElogE) | O(ElogV) | O(ElogV) |
프림과 다익스트라는 코드 구조가 거의 동일하다. 유일한 차이는 PQ에 넣는 값이 "간선 가중치만"이냐 "누적 거리"냐다.
10. 오늘 리뷰
위상 정렬에서 사이클 감지가 자연스럽게 된다는 게 인상 깊었다. 결과 리스트 크기가 N보다 작으면 사이클이 있다는 것이다. 사이클이 있으면 진입 차수가 0이 되는 정점이 없어서 큐에서 꺼낼 게 없어진다.
한 알고리즘이 여러 기능을 동시에 한다는 게 좋은 알고리즘의 특징 같다. 크루스칼에서 union이 false를 반환하면 사이클 감지가 되고, 위상 정렬에서 결과 개수로 사이클 감지가 된다.
11. 키워드 정리
프림 위상 정렬
12. 내일의 목표
- DP(Dynamic Programming) 입문
- 백준 문제 풀이
