[백준] 1197번 최소 스패닝 트리 C++ 문제풀이

문제 풀이

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 의미한다.

최소 스패닝 트리를 만드는 방법에는 크게 Prim 알고리즘, Kruskal 알고리즘이 있는데 결국은 Greedy를 이용한 알고리즘이다.

Kruskal 알고리즘은 맨 처음 각 정점마다 집합을 만든다고 생각하고, Edge를 연결할 때는 서로소인 집합인 경우에만 연결한다.

이를 위해서 맨 처음 가중치를 오름차순으로 정렬하고, 두 정점이 서로소인 집합인지를 확인하면서 연결하면 된다.

Edge의 수는 정점의 수 - 1 개이므로 cnt  = n-1일 때 까지 위의 과정을 반복하면 된다.

소스 코드

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

long long int result = 0;
int parent[10001] = { 0 };
vector<pair<int, pair<int, int>>> tree;

int find(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
	parent[y] = x;
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		tree.push_back(make_pair(c, make_pair(a, b)));
	}
	// 오름차순으로 정렬
	sort(tree.begin(), tree.end());
	
	int cnt = 0;
	int idx = 0;
	// 최소 스패닝 트리 찾기
	while (cnt < n - 1) {
		int w = tree[idx].first;
		int x = tree[idx].second.first;
		int y = tree[idx].second.second;
		int p = find(x);
		int q = find(y);
		if (p != q) { // 서로소 집합인 경우 이어준 다음 집합을 합침
			merge(p, q); // 집합을 합침
			result += w;
			cnt += 1;
		}
		idx += 1;
	}
	cout << result << '\n';
}