알고리즘/알고리즘 문제 풀이
(C++) 백준 1197번 - 최소 스패닝 트리
용꿀
2023. 6. 19. 05:15
문제 링크 : https://www.acmicpc.net/problem/1197
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
풀이
Union-Find를 사용해서 크루스칼 알고리즘을 구현하여 최소 신장 트리의 크기를 구해보았다.
정렬 시에 가장 처음에 나타난 값을 기준으로 정렬하기에, cost 값을 튜플에 맨 앞에 위치시켜야 한다는 점을 간과하여 오랜 시간을 낭비하기도 했다.
#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
int parent[100005];
tuple<int, int, int> t[100005];
int v, e, cost, x, y, result, cnt;
int find(int x){
if(parent[x] == x) return x;
else return parent[x] = find(parent[x]);
}
void uni(int x, int y){
x = find(x);
y = find(y);
parent[y] = x;
}
bool is_diff_group(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
else return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> v >> e;
for(int i = 0; i < e; i++){
cin >> x >> y >> cost;
t[i] = {cost, x, y};
}
sort(t, t+e);
for(int i = 1; i <= v; i++) parent[i] = i;
for(int i = 0; i < e; i++){
if(!is_diff_group(get<1>(t[i]), get<2>(t[i]))) continue;
uni(get<1>(t[i]), get<2>(t[i]));
result += get<0>(t[i]);
cnt++;
if(cnt == v-1) break;
}
cout << result;
}