백준 1922 네트워크 연결 (C++)

1922번: 네트워크 연결

최소 스패닝 트리를 이용한 문제이다. 이전에 풀었던 MST와 알고리즘이 완전 똑같다고 볼 수 있다. 중요한 점은 정렬을 통해 비용이 낮은 순부터 합쳐주어 결과적으로 최소 비용이 나온다는 점이다.
MST를 떠올리지 못하고 알고리즘 분류를 보고 생각해냈다. MST를 알아두자.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M, res = 0;
int parent[1001];
vector < pair<int, pair<int, int>>> v;

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

void unionParent(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	if (a != b) parent[b] = a;
}

bool sameParent(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	if (a == b) return true;
	else return false;
}

void solution() {
	sort(v.begin(), v.end());

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

	for (int i = 0; i < M; i++) {
		int a = v[i].second.first;
		int b = v[i].second.second;
		int cost = v[i].first;

		if (!sameParent(a, b)) {
			unionParent(a, b);
			res += cost;
		}
	}

	cout << res;
}

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

	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		v.push_back({ c,{a,b} });
	}

	solution();
	
	return 0;
}