백준 1197 최소 스패닝 트리 (c++) : 피너클

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

1197번: 최소 스패닝 트리

최소 스패닝 트리 문제다.

최소 스패팅 트리는 그래프의 모든 정점을 연결하는데 필요한 가중치중 가장 작은 가중치를 구하는 알고리즘이다.

인터넷에 치면 많이 나오는 알고리즘이니 따로 설명은 안하겠다. 여기선 크루스칼을 사용할것이다.

int v, e;
vector<pair<int, int>> adj[10001];
vector<int> parent(10001);
vector<int> rnk(10001, 1);

사용할 변수다. 

adj는 가중치를 입력받을때 사용할것이다.

parent와 rnk는 유니온 파인드에 사용할것이다.

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}

find함수다. num의 조상이 누군지를 리턴한다.

void merge(int _u, int _v) {
	int u = find(_u), v = find(_v);
	if (u == v) return;
	if (rnk[u] > rnk[v]) swap(u, v);
	parent[u] = v;
	if (rnk[u] == rnk[v]) rnk[u]++;
}

merge함수다. _u와 _v를 합칠때 사용한다.

이때 그냥 합치는것이 아닌 둘중 높이가 적은 쪽으로 합친다. 여기서 rnk가 사용된다.

rnk[i]는 i의 깊이를 의미한다. _u와 _v중 rnk값이 더 작은 쪽으로 합치기 위해 rnk[u]가 rnk[v]보다 클때 서로 swap한다.

만약 서로의 높이가 같다면 rnk에 1을 더해줘야한다.

cin >> v >> e;
for (int i = 0; i < e; i++) {
	int a, b, c;
	cin >> a >> b >> c;
	adj[a].push_back({ b, c });
	adj[b].push_back({ a, c });
}
cout << kuruskal() << endl;

이제 메인함수에서 값들을 입력받는다.

가중치를 입력받을때는 양방향으로 입력받아준다.

그후 kuruskal함수를 돌려준다. 스펠링이 맞는지는 나도 모른다.

int kuruskal() {
	for (int i = 0; i <= v; i++) parent[i] = i;
	int ans = 0;
	vector < pair<int, pair<int, int>>> edges;
	for (int i = 0; i < v; i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			int u = adj[i][j].first, cost = adj[i][j].second;
			edges.push_back({ cost, {i, u} });
		}
	}

크루스칼 함수다. 먼저 parent를 전부 자기 자신으로 초기화해준다.

ans는 최소 가중치다.

edges에는 {가중치, {출발점, 도착점}} 이 들어간다.

	sort(edges.begin(), edges.end());

그후 edges를 가중치를 기중으로 정렬한다.

	for (int i = 0; i < edges.size(); i++) {
		int cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;

		if (find(u) == find(v)) continue;
		ans += cost;
		merge(u, v);
	}

그후 edges 크기만큼 반복문을 돌린다.

cost는 가중치, u는 출발점, v는 도착점이다.

만약 u와 v의 조상이 같다면 뒤를 무시한다.

먄약 u와 v의 조상이 다르다면 아직 둘은 연결되지 않은것이다. ans에 cost를 더하고 둘을 merge함수로 합친다.

	return ans;
}

그후 ans를 리턴한다.

유니온 파인드만 알면 쉽게 이해할수있는 알고리즘이다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int v, e;
vector<pair<int, int>> adj[10001];
vector<int> parent(10001);
vector<int> rnk(10001, 1);

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}

void merge(int _u, int _v) {
	int u = find(_u), v = find(_v);
	if (u == v) return;
	if (rnk[u] > rnk[v]) swap(u, v);
	parent[u] = v;
	if (rnk[u] == rnk[v]) rnk[u]++;
}

int kuruskal() {
	for (int i = 0; i <= v; i++) parent[i] = i;
	int ans = 0;
	vector < pair<int, pair<int, int>>> edges;
	for (int i = 0; i < v; i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			int u = adj[i][j].first, cost = adj[i][j].second;
			edges.push_back({ cost, {i, u} });
		}
	}
	sort(edges.begin(), edges.end());
	for (int i = 0; i < edges.size(); i++) {
		int cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;

		if (find(u) == find(v)) continue;
		ans += cost;
		merge(u, v);
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> v >> e;
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	cout << kuruskal() << endl;
}

전체코드다.