백준 1197 : 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

이름 그대로 정직하게 최소 스패닝 트리 문제다.

크루스칼 알고리즘으로 유니온-파인드로 쉽게 해결할 수 있다.

 

1. 초기 부모 정보는 자기 자신으로 설정한다.

2. 간선은 우선순위큐를 사용하여 간선의 가중치를 기준으로 오름차순으로 정렬한다.

3. 간선의 가중치가 작은 순서대로 유니온 작업을 수행한다.

 

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;
using tiii = tuple<int, int, int>;

int v, e;
int parent[10'001];
priority_queue<tiii> edge;

// 부모 찾기, 압축
int ffind(int x) {
	if (x == parent[x]) return x;
	else return parent[x] = ffind(parent[x]);
}

// union 작업 수행
bool funion(int x, int y) {
	x = ffind(x);
	y = ffind(y);

	if (x == y) return 0;

	if (x < y) {
		int tmp = y;
		y = x, x = tmp;
	}

	parent[x] = y;
	return 1;
}

void solution() {
	int a, b, c, ans = 0;
	cin >> v >> e;
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		// c가 작은 순서대로 pq에 정렬
		edge.emplace(-c, a, b);
	}
	// 부모 초기값을 자기 자신으로 설정
	for (int i = 1; i <= v; i++) parent[i] = i;

	// 유니온이 필요한 경우 수행하고 간선의 가중치를 더해줌
	while (!edge.empty()) {
		tie(c, a, b) = edge.top();
		edge.pop();
		if (funion(a, b)) ans -= c;
	}
	cout << ans;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 4496 kb

시간: 44 ms