BOJ (C/C++) 1922번: 네트워크 연결

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

1922번: 네트워크 연결

---

풀이

최소 스패닝 트리를 구하는 문제 -> 크루스칼 알고리즘 사용

 

크루스칼? 연결 비용을 오름차순으로 정렬하여 가장 적은 비용부터 사용함

두 노드가 같은 그룹에 속하지 않았을 때 이어주는 간선을 사용하여 비용을 증가시킴

---

코드

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

vector <pair<int, pair<int, int >>> Com;
int R[1001];

int Find(int n) {
	if (R[n] == n) return n;
	return Find(R[n]);
}
void Union(int a, int b) {
	int aroot, broot;
	aroot = Find(a);
	broot = Find(b);
	R[broot] = aroot;
}

int Kruskal(int N) {
	int start, end, cost = 0;

	// asc
	sort(Com.begin(), Com.end());

	// 루트는 자기 자신으로 초기화
	for (int i = 1; i <= N; i++) R[i] = i;

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

		// 두 노드가 같은 그룹에 속하지 않았을 때
		if (Find(start) != Find(end)) {
			cost += Com[i].first;

			// 노드의 root 연결
			Union(start, end);
		}
	}
	return cost;
}

int main() {
	int N, M, a, b, c;

	scanf("%d\n%d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &a, &b, &c);
		Com.push_back({ c,{a,b} });
	}

	printf("%d", Kruskal(N));
	return 0;
}