1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
최소 스패닝 트리(MST)의 기본 연습문제입니다.
크루스칼 알고리즘과 프림 알고리즘 둘 다 사용하였습니다.
크루스칼 알고리즘은 가중치가 낮은 순으로 간선을 골라주시면 되는데 사이클 방지를 위해 Union-find를 이용합니다.
뽑은 간선의 두 정점을 union-find로 이어주고 parent를 같게합니다.
그 다음에 뽑은 간선의 두 정점의 parent가 같으면 사이클이 발생하므로 제외시켜주는 방식입니다.
프림 알고리즘은 한 정점을 임의로 정하여 bfs와 비슷한 방식으로 순회하는데
방문한 정점에 연결된 간선 모두를 우선순위 큐에 넣고
다음 방문할 정점은 큐에 있는 정점 중 가중치가 가장 낮은 정점입니다.
만약 이미 방문하여 연결된 간선 모두를 큐에 넣었던 정점이면 continue를 해주고 방문하지 않은 정점에 연결된 간선만 모두 추가합니다.
두 방식 모두 N - 1개의 간선을 골랐으면 break를 하고 지금까지 더했던 가중치를 출력해줍니다.
[Kruskal]
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef struct Point { int u; int v; int w; }; vector<Point> list; int parent[10001]; int N, M, ans, cnt; bool cmp(Point a, Point b) { if (a.w < b.w) return true; else return false; } void init() { for (int i = 1; i <= N; i++) { parent[i] = i; } } int find(int v) { if (parent[v] == v) return v; return parent[v] = find(parent[v]); } void Union(int x, int y, int w) { int a = find(x); int b = find(y); if (a == b) return; parent[b] = a; ans += w; cnt++; } void func() { for (int i = 0; i < M; i++) { int u = list[i].u; int v = list[i].v; int w = list[i].w; Union(u, v, w); if (cnt == N - 1) break; } cout << ans << '\n'; } void input() { int u, v, w; cin >> N >> M; for (int i = 0; i < M; i++) { cin >> u >> v >> w; list.push_back({ u,v,w }); } sort(list.begin(), list.end(), cmp); } int main() { cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); input(); init(); func(); return 0; } | cs |
[Prim]
|
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
49
50
51
52
53
54
55
56
57
58
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int, int> > list[10001];
bool visit[10001];
int N, M, ans, cnt;
void func() {
priority_queue<pair<int, int> > q;
for (int i = 0; i < list[1].size(); i++) {
q.push({ -list[1][i].second, list[1][i].first });
}
visit[1] = true;
while (!q.empty()) {
int x = q.top().second;
int w = -q.top().first;
q.pop();
if (visit[x]) continue;
visit[x] = true;
ans += w;
cnt++;
if (cnt == N - 1) break;
for (int i = 0; i < list[x].size(); i++) {
int next = list[x][i].first;
int nextw = list[x][i].second;
q.push({ -nextw, next });
}
}
cout << ans << '\n';
}
void input() {
int u, v, w;
cin >> N >> M;
while(M--) {
cin >> u >> v >> w;
list[u].push_back({ v, w });
list[v].push_back({ u, w });
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > MST' 카테고리의 다른 글
| boj 1647 도시 분할 계획 (0) | 2021.03.19 |
|---|---|
| boj 1922 네트워크 연결 (0) | 2021.03.19 |