BOJ 1922 네트워크 연결

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

이산수학에서 최소 스패닝 트리를 구하는 방법에 대해 공부하길래 이왕 하는 겸 알고리즘으로 풀어보고 싶어서

구현해봤다. 처음에는 프림 알고리즘 먼저 구현해보려 했는데 유니온 파인드도 복습할 겸 해서 크루스칼로 풀었다.

 

int find(int x) {
	return p[x] < 0 ? x : p[x] = find(p[x]);
}

bool merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return false;
	p[y] = x;
	return true;
}

 

find는 각 노드의 루트 노드를 찾아서 반환해주고

merge는 크루스칼 알고리즘에 최적화시켜줬다.

 

크루스칼 알고리즘은 우선 E를 입력받은 후 E에 대해서 오름차순으로 정렬한 뒤 

가중치의 최솟값에 대해서 같은 집합이 아니라면 갱신해주는데 이때 갱신이 총 V - 1 번 일어나면

바로 종료한다.

 

따라서 merge함수를 같은 집합이라면 false, 다른 집합이라면 갱신해야 하니 true를 반환해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct P { int u, v, w; };
vector<P> ar;
vector<int> p;
int n, m, a, b, c, ans, cnt;

int find(int x) {
	return p[x] < 0 ? x : p[x] = find(p[x]);
}

bool merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return false;
	p[y] = x;
	return true;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	p.resize(n + 1, -1);
	ar.resize(m);

	for (int i = 0; i < m; ++i) {
		cin >> a >> b >> c;
		ar[i] = { a - 1,b - 1,c };
	}

	sort(ar.begin(), ar.end(),
		[](const P& a, const P& b) { return a.w < b.w; });

	for (int i = 0;; ++i) {
		if (merge(ar[i].u, ar[i].v)) {
			ans += ar[i].w;
			if (++cnt == n - 1) break;
		}
	}

	cout << ans << endl;

	return 0;
}