[백준 BOJ][C++]1197번 최소 스패닝 트리 풀이 - Kruskal MST 알고리즘

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

1197번: 최소 스패닝 트리

 

 

[ 풀이 과정 ]

 

1. 입력 정보를 받는다. 

2. 간선의 정보를 가중치 오름차순 우선순위 큐 edges에 추가한다. 

3. 각 정점들의 root 정점을 자기 자신으로 설정한다.  parent[i] = i

4. edges에서 간선을 pop 한다. 

5. 해당 간선에 양 끝 정점의 root 정점이 같다면 4 단계로 돌아간다. 

6. 양 끝 정점의 root 정점이 다르다면 root 정점을 동일하게 한 뒤, 가중치 합에 해당 간선의 가중치를 더한다. 

7. 모든 간선을 검사할 때까지 4~6 과정을 반복한다. 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>

using namespace std;

int v, e;
int parent[10001];
long long ans;
bool check;

typedef struct edge {
	int v1;
	int v2;
	int w;
};

struct compare {
	bool operator()(edge a, edge b) {
		return a.w > b.w;
	}
};

priority_queue < edge, vector<edge>, compare> edges;

int find(int x) {
	if (parent[x] == x)
		return x;

	return parent[x] = find(parent[x]);
}

void union_set(int x, int y) {
	check = false;

	int root_x = find(x);
	int root_y = find(y);

	if (root_x == root_y)
		return;

	parent[root_x] = root_y;
	check = true;
}


void mst() {

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

	while (!edges.empty()) {
		int x = edges.top().v1;
		int y = edges.top().v2;
		int w = edges.top().w;
		edges.pop();

		union_set(x, y);
		if (check) {
			ans += w;
		}
	}
}

int main(void) {

	cin >> v >> e;

	for (int i = 0; i < e; i++) {
		int v1, v2, w;
		cin >> v1 >> v2 >> w;
		edge temp = { v1, v2, w };
		edges.push(temp);
	}

	mst();
	cout << ans << endl;
	
	return 0;
}