BOJ 1197 | 최소 스패닝 트리

최소 스패닝 트리를 구현하라는 아주 간단한 문제다.

나는 크루스칼 알고리즘으로 구현했는데 이게 아주 편해서 프림 알고리즘은 생각도 안 날 정도다 ㅋㅋㅋㅋ

Union Find 클래스를 만들어 놓으니까 문제 풀기에 아주 좋다.

아직 최소 스패닝 트리의 응용 문제를 안 봤는데 어떻게 이 구조가 사용될지 아주 궁금하다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

class UnionFind{
private:
	vector<int> parent;
public:
	UnionFind(int n){
		parent.resize(n+1);
		for (int i = 0; i <= n; i++){ // parent[i] = i's parent
			parent[i] = i;
		}
	}
	int Find(int x){
		if (x == parent[x]) return x;
		return parent[x] = Find(parent[x]);
	}
	void Union(int x, int y){
		x = Find(x);
		y = Find(y);
		parent[y] = x;
	}
	vector<int> tree(){
		return parent;
	}
};

struct Node{
	int l, r;
	int w;
};

bool cmp(Node x, Node y){
	return x.w < y.w;
}

int main(){
	FASTIO;
	
	int N, M; cin >> N >> M;
	UnionFind S = UnionFind(N);
	vector<Node> node;
	
	for (int i = 0; i < M; i++){
		int x, y, w; cin >> x >> y >> w;
		node.push_back({x, y, w});
	}
	
	sort(node.begin(), node.end(), cmp);
	
	int sum = 0;
	
	for (auto &i : node){
		if (S.Find(i.l) != S.Find(i.r)){
			S.Union(i.l, i.r);
			sum += i.w;
		}
	}
	
	cout << sum;
	
}