백준 1197. 최소 스패닝 트리

최소 스패닝 트리

 

---

Problem?

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

Input

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 N번까지 번호가 매겨져 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

 

Output

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

Solution

kruskal algorithm을 사용해서 풀었다.

Find와 Union 모두 Simple Find와 Simple Union으로 구현하였다.
(해당 문제를 Collapsing Find와 Weighted Union으로 문제를 풀었는데 시간 초과가 났다.)

가정 simpleFind(int x) : 부모 찾기 simpleUnion(int x, int y) : 부모 이어 주기   graph : 해당 input의 그래프

Code

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

#define MAX 10000 + 1

int V, E;
int parent[MAX];
vector<pair<int, pair<int, int>>> graph;

int simpleFind(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = simpleFind(parent[x]);
}

void simpleUnion(int x, int y) {
	int x_parent = simpleFind(x);
	int y_parent = simpleFind(y);
	if (x_parent != y_parent)
		parent[x_parent] = y_parent;
}

int main() {
	int start_pos, end_pos, weight;
	long long int ans = 0;

	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &start_pos, &end_pos, &weight);
		graph.push_back(make_pair(weight, make_pair(start_pos, end_pos)));
	}
	sort(graph.begin(), graph.end());

	for (int i = 1; i <= V; i++)
		parent[i] = i;

	for (int i = 0; i < E; i++) {
		if (simpleFind(graph[i].second.first) != simpleFind(graph[i].second.second)) {
			simpleUnion(graph[i].second.first, graph[i].second.second);
			ans += graph[i].first;
		}
	}

	cout << ans << "\n";
	return 0;
}

 

---

과거 알고리즘 수업들을 때는 극단적인 경우(한쪽으로 쏠리는 경우)를 막기 위해서 Simple Find와 Simple Union보다는 Collapsing Find와 Weighted Union이 좋다고 했는데, 이 문제에서는 왜인지 적용이 되지 않았다.

 

일반적인 경우는 Simple이 더 나은 것인지, 코드상에 문제가 있었는지 확인해봐야겠다.