[백준 1197] 최소 스패닝 트리

문제 풀이

 

간단하게 MST 알고리즘을 구현할 수 있는지 물어보는 문제다.

그중에서도 크루스칼 알고리즘을 이용해서 풀었다.

 

크루스칼 알고리즘은 유니온 파인드와 정렬을 이용해서 MST를 구상하게 된다.

따라서 기본적인 크루스칼 알고리즘을 구현하면 문제를 해결할 수 있다.

 

소스 코드

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

const int MAX = 10001;
int V, E;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];

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

void unionParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void input()
{
	cin >> V >> E;
	for (int i = 0; i < E; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({ c, {a,b} });
	}

	for (int i = 1; i <= V; i++) parent[i] = i;
}

void solve()
{
	input();

	sort(edges.begin(), edges.end());

	long long ans = 0;
	int len = edges.size();
	for (int i = 0; i < len; i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (findParent(a) != findParent(b))
		{
			unionParent(a, b);
			ans += cost;
		}
	}

	cout << ans << endl;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}