문제 풀이
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 의미한다.
최소 스패닝 트리를 만드는 방법에는 크게 Prim 알고리즘, Kruskal 알고리즘이 있는데 결국은 Greedy를 이용한 알고리즘이다.
Kruskal 알고리즘은 맨 처음 각 정점마다 집합을 만든다고 생각하고, Edge를 연결할 때는 서로소인 집합인 경우에만 연결한다.
이를 위해서 맨 처음 가중치를 오름차순으로 정렬하고, 두 정점이 서로소인 집합인지를 확인하면서 연결하면 된다.
Edge의 수는 정점의 수 - 1 개이므로 cnt = n-1일 때 까지 위의 과정을 반복하면 된다.
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long int result = 0;
int parent[10001] = { 0 };
vector<pair<int, pair<int, int>>> tree;
int find(int x) {
if (parent[x] == x)
return x;
else
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
parent[y] = x;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
tree.push_back(make_pair(c, make_pair(a, b)));
}
// 오름차순으로 정렬
sort(tree.begin(), tree.end());
int cnt = 0;
int idx = 0;
// 최소 스패닝 트리 찾기
while (cnt < n - 1) {
int w = tree[idx].first;
int x = tree[idx].second.first;
int y = tree[idx].second.second;
int p = find(x);
int q = find(y);
if (p != q) { // 서로소 집합인 경우 이어준 다음 집합을 합침
merge(p, q); // 집합을 합침
result += w;
cnt += 1;
}
idx += 1;
}
cout << result << '\n';
}
'알고리즘' 카테고리의 다른 글
[백준] 1647번 도시 분할 계획 C++ 문제풀이 (0) | 2024.01.18 |
---|---|
[백준] 11049번 행렬 곱셈 순서 C++ 문제풀이 (0) | 2024.01.16 |
[백준] 10942번 팰린드롬? C++ 문제풀이 (0) | 2024.01.12 |
[백준] 27172번 수 나누기 게임 C++ 문제풀이 (1) | 2024.01.11 |
[백준] 17404번 RGB거리 2 C++ 문제풀이 (0) | 2024.01.10 |