[1197] 최소 스패닝 트리, c++

<네이버에서 옮겨온 것>

 

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

1197번: 최소 스패닝 트리

1. [1197] 최소 스패닝 트리

 

한줄 후기 : MST는 재밌어

 

 

최소 스패닝 트리 성공분류

Gold IV

그래프 이론최소 스패닝 트리

난이도 제공: solved.ac — 난이도 투표하러 가기

---

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	23392	9826	5350	38.898%

 

문제

 

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

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

 

입력

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

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

 

출력

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

 

예제 입력 1

3 3 1 2 1 2 3 2 1 3 3

 

예제 출력 1

3

 

이 문제는 단순하게 MST를 구하면 되는 문제. 그러나 전 크루스칼의 알고리즘으로 푸느라 개 고생 했음

프림의 알고리즘으로 풀면 더 쉬울듯.

 

지금은 크루스칼이 더 좋음

 

//AC
//BOJ 1197 최소 스패닝 트리
//https://www.acmicpc.net/problem/1197 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10001
using namespace std;
struct Edge{
	int start, end, cost;
	bool operator < (const Edge& other) const{
		return cost < other.cost;
	}
};
int parent[MAX];
int Find(int x){
	if(parent[x]==x)	return x;
	else	return parent[x]=Find(parent[x]);
}
void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	parent[y] = parent[x];
}
int main(){
	int v, e, ans=0;
	cin >> v >> e;
	for(int i=1; i<=v; i++){
		parent[i] = i;
	}
	vector<Edge> graph(e);
	for(int i=0; i<e; i++){
		cin >> graph[i].start >> graph[i].end >> graph[i].cost;
	}
	sort(graph.begin(), graph.end());
	for(int i=0; i<e; i++){
		if(Find(graph[i].start)!=Find(graph[i].end)){
			ans += graph[i].cost;
			Union(Find(graph[i].start), Find(graph[i].end));
		}
	}
	printf("%d", ans);
	return 0;
}

 

크루스칼의 알고리즘을 구현하기 위해서는 Union-Find라는 자료구조를 알아야 합니다. Union은 두 정점들의 집합 합치는 것이고, Find는 부모 노드를 반환해 준다고 생각하면 된다.

최소 비용을 구해야 하기 때문에 그래프를 cost 기준으로 sort한 후 Find 연산을 통한 비교( 부모노드가 같다면 이미 한번 병합되어 볼 필요 X) 후 cost 를 누적시킨 후 Union 연산으로 정점 집합을 합치자.

마지막에 누적된 값이 최소 스패닝 트리.