[Baekjoon] 1197번: 최소 스패닝 트리

🥅 문제

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

 

🔍 설계

단순히, 최소 스패닝 트리를 구현하는 문제이다. 

 

최소 스패닝 트리를 어떻게 구현하는지 복기해보자.

 

1. 간선 정보를 비용을 기준으로 오름차순으로 정렬한다. 본인은 우선순위 큐를 사용하였다.

2. 우선순위 큐에서 하나씩 꺼내서(= 비용이 작은 간산부터) 두 정점을 연결 시도한다. 두 정점의 부모가 같은 경우, 이미 연결되어 있다는 뜻이므로 넘어간다. 두 정점의 부모가 다른 경우, 연결되어 있지 않다는 의미이므로 union을 통해 연결하고 가중치에 비용을 추가한다.

 

👊 풀이

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

int v, e, a, b, c, result = 0;
vector<int> parent(10001);
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> edges;

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

void union_parent(int a, int b) {
	if (a > b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	

	cin >> v >> e;

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

	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		edges.push({ c, a, b });
	}

	while (!edges.empty()) {
		int c = edges.top()[0];
		int a = edges.top()[1];
		int b = edges.top()[2];
		edges.pop();

		a = find_parent(a);
		b = find_parent(b);

		if (a != b) {
			union_parent(a, b);
			result += c;
		}
	}

	cout << result << "\n";

	return 0;
}