문제
풀이
최소 신장 트리를 형성하는 알고리즘에는 크게 두 가지가 있다. 크루스칼(Kruscal) 알고리즘과 프림(Prim) 알고리즘이 있다. 크루스칼 알고리즘은 그리디 알고리즘에 속해있다. 먼저, 간선의 가중치들을 오름차순으로 sort를 한다. 그 이후, 작은 것부터 차례대로 간선을 union, 집합을 형성한다. 만약 이 때, 집합을 형성하려고 할 때 사이클이 형성된다면 그 간선은 집합에 넣지 않고 다음 간선으로 진행한다. 모든 정점이 선으로 연결될 때까지 진행을 하면 최소 신장 트리를 만들어낼 수 있다. 꼭지점의 개수를 V, 간선의 개수를 E라고 할 때 시간 복잡도는 O(ElogV)이다. 프림 알고리즘은 임의의 정점을 골라, 그 인접한 간선 중에 최소 가중치를 갖는 정점을 선택하여, 정점 갯수 - 1 개의 간선이 될 때까지 진행하는 방법이다. 간선의 수가 적으면 크루스칼, 정점의 수가 적으면 프림이 유리하다고 한다. 시간복잡도는 이진 힙을 이용하면 O(ElogV), 피보나치 힙을 이용하면 O(E+VlogV)이다. 해당 문제는 크루스칼 알고리즘을 통해 sort를 한 뒤 merge가 완료되면 value들을 덧셈해 나가는 식으로 정답을 도출해나갔다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, pair<int, int>>> map;
int parent[10001];
int cost;
int find(int x){
if(parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
bool merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
parent[x] = y;
return true;
}
int main(){
int N, M;
scanf("%d %d", &N, &M);
for(int i = 0; i<=N; i++){
parent[i] = -1;
}
for(int i = 0; i<M; i++){
int from, to, value;
scanf("%d %d %d", &from, &to, &value);
map.push_back(make_pair(value, make_pair(from, to)));
}
sort(map.begin(), map.end());
for(int i = 0; i<map.size(); i++){
if(merge(map[i].second.first, map[i].second.second)){
cost += map[i].first;
}
}
printf("%d\n", cost);
}
