[BOJ/백준] 1197 - 최소 스패닝 트리

1197번: 최소 스패닝 트리

---

---

---

• 제목

최소 스패닝 트리

---

• 조건

시간 제한 : 1 초

메모리 제한 : 128 MB 

---

• 문제

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

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

---

• 입력

첫째 줄에 정점의 개수 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	예제 출력1
3 3 1 2 1 2 3 2 1 3 3	3

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define VMAXSIZE 10001
#define EMAXSIZE 100001

vector<pair<int, pair<int,int>>> vt;

int V, E, from;
int parent[VMAXSIZE];

// UnionFind Algorithm -> Disjoint-Set
int Find(int x){
	if(x == parent[x]) return x;
	else return Find(parent[x]);
}
void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y) parent[y] = x;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
 	int to, cost, sum = 0;
	cin >> V >> E;
	for(int n = 0 ; n < E ; n++){
		cin >> from >> to >> cost;
		vt.push_back(make_pair(cost, make_pair(from, to)));
	}
	// sort vector
	sort(vt.begin(), vt.end());

	//	default parent for cycle check
	for(int n = 1; n <= V; n++) parent[n] = n;

	for(int n = 0; n < E; n++){
		int x = vt[n].second.first;
		int y = vt[n].second.second;
		int c = vt[n].first;
		
		// cycle check
		if(Find(x) == Find(y)) continue;

		// weight sum
		sum += c;
		// union
		Union(x, y);
	}
	cout << sum << endl;
    return 0;
}