BOJ (C/C++) 1197번: 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

---

풀이

최소 스패닝 트리를 구하는 문제이므로 union-find와 크루스칼 알고리즘을 사용했다.

(가중치 오름차순으로 정렬 후 작은 가중치 값부터 더하며 집합을 합쳐주었다.)

 

음수인 가중치가 있지만, 최단 경로를 구하는 게 아니라 크루스칼이 가능할 거라 판단했다.

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <pair<int, pair<int, int>>> G;
int root[10001];

int Find(int a) {
	if (root[a] == a) return a;
	return Find(root[a]);
}
void Union(int a, int b) {
	int roota, rootb;
	roota = Find(a);
	rootb = Find(b);
	root[rootb] = roota;
}

void Kruskal(int size) {
	int start, end, value;
	long long int sum = 0;

	for (int i = 0; i < size; i++) {
		value = G[i].first, start = G[i].second.first, end = G[i].second.second;

		// 같은 그룹에 속하면 계산할 필요 x
		if (Find(start) == Find(end)) continue;

		Union(start, end);
		sum += value;
	}

	printf("%lld", sum);
}
int main() {
	int V, E;
	int a, b, c;

	// input
	scanf("%d %d", &V, &E);
	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &a, &b, &c);
		G.push_back({ c,{a,b} });
	}

	// init
	for (int i = 1; i <= V; i++) root[i] = i; // 초기 루트는 자기 자신
	sort(G.begin(), G.end()); // 오름차순 정렬

	Kruskal(E);

	return 0;
}