[백준 1922] 네트워크 연결

문제 풀이

 

모든 컴퓨터를 연결하는데 최소한의 비용으로 연결하려면 MST 알고리즘을 구현하면 됩니다.

MST 중 유명한 알고리즘인 크루스칼 알고리즘을 이용해서 구현하면 해결할 수 있습니다.

 

소스 코드

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

const int MAX = 1001;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
int N, M;

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 >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({ c, {a,b} });
	}

	sort(edges.begin(), edges.end());
	for (int i = 1; i <= N; i++) parent[i] = i;
}

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

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