최소 스패닝 트리
문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
개념 : 방향없는 그래프에서 모든 노드를 포함하면서, 순환되는 경로를 제거한 현태를 스패닝 트리(Spanning Tree) 라고 한다. 이 스패일 트리에서 가중치의 합을 최소로 만드는 스패닝 트리를 최소 스패닝트리(Minimal Spanning Tree)라고 한다. 최소 스패닝 트리를 만들기 위한 방법으로는 크루스칼 알고리즘을 이용한다!
크루스칼 알고리즘에 대해서는 한빛미디어 - 이것이코딩테스트다 with python 을 참고하시길 바랍니다.
unionParent, findParent는 여러 알고리즘을 풀면서 종종 이용해 먹을만한 개념이라고 생각한다.
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int parent[10001];
int ans;
struct node {
int val, x, y;
node(int val, int x, int y)
{
this->val = val;
this->x = x;
this->y = y;
}
};
vector<node> v;
int findParent(int x)
{
if (x == parent[x]) return x;
else return parent[x] = findParent(parent[x]);
}
bool sameParent(int x, int y)
{
x = findParent(x);
y = findParent(y);
if (x == y)return true;
else return false;
}
void unionParent(int x, int y)
{
x = findParent(x);
y = findParent(y);
if (x > y) parent[x] = y;
else parent[y] = x;
}
bool compare(node& a, node& b)
{
return a.val < b.val;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
v.push_back(node( c,a,b ));
}
sort(v.begin(), v.end(), compare);
for (int i = 0; i < n; i++)
parent[i] = i;
for (int i = 0; i < v.size(); i++)
{
if (!sameParent(v[i].x, v[i].y))
{
unionParent(v[i].x, v[i].y);
ans += v[i].val;
}
}
cout << ans;
return 0;
}
|
cs |
'Programming > Algorithm' 카테고리의 다른 글
| [Simulation, BOJ-12100] 2048(Easy), c++ (0) | 2021.05.10 |
|---|---|
| [graph theory, BOJ-13460] 구슬 탈출2, c++ (0) | 2021.05.09 |
| [graph theory, BOJ-2206] 벽부수고 이동하기, c++ (0) | 2021.05.03 |
| [graph theory, BOJ-1753] 최단경로, c++ (0) | 2021.04.26 |
| [graph theory, BOJ - 14502] 연구소, c++ (0) | 2021.04.25 |