[백준 BoJ] 1922 - 네트워크 연결

// https://www.acmicpc.net/problem/1922
// 네트워크 연결
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
int N, M;
bool visited[1002];
vector<vector<pair<int, int>>> edges;
priority_queue<pair<int, int>> pq;
int ans = 0;
void prim(int start) {
	visited[start] = true;
	for (auto e : edges[start]) {
		int cost = e.second;
		int to = e.first;
		pq.push(make_pair(-cost, to));
	}

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int to = pq.top().second;
		pq.pop();

		if (!visited[to]) {
			ans += cost;
			visited[to] = true;
			for (auto e : edges[to]) {
				int nextCost = e.second;
				int nextTo = e.first;
				if (!visited[nextTo]) {
					pq.push(make_pair(-nextCost, nextTo));
				}
			}
		}
	}

}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	edges.resize(N + 1);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges[a].push_back(make_pair(b, c));
		edges[b].push_back(make_pair(a, c));
	}

	prim(1);
	cout << ans;
}

// https://www.acmicpc.net/problem/1922
// 네트워크 연결
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int N, M, parent[1002];
vector<tuple<int, int, int>> Network;

bool cmp(tuple<int, int, int> a, tuple<int, int, int> b){
	return get<2>(a) < get<2>(b);
}
int Find(int x) {
	if (parent[x] == x) return x;
	return parent[x] = Find(parent[x]);
}

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

void kruskal() {
	int sum = 0;
	for (auto n : Network) {
		int a = get<0>(n);
		int b = get<1>(n);
		int cost = get<2>(n);
		if (Find(a) != Find(b)) {
			sum += cost;
			Union(a, b);
		}
	}
	cout << sum;
}
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < M; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		Network.push_back(make_tuple(from, to, cost));
	}

	sort(Network.begin(), Network.end(), cmp);
	kruskal();
}

• MST(Minimum Spanning Tree)
• 크루스칼
• 프림