문제 출처

1. 문제설명

• 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하라
  • 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리
• 문제 분류
  • Graph, MST(Minimum Spanning Tree)

2. 알고리즘 설계

• MST 기본 문제이다.
  • 이에 대한 설명은 여기에 정리해두었다.
• 크게 크루스칼 또는 프림 알고리즘이 있는데, 이 문제에서는 크루스칼을 채택했다.
  • 크루스칼은 간선이 같은 그룹인지 아닌지가 초점인 알고리즘이다.
• 참고로 크루스칼을 효율적으로 구현하기 위해서는 union-find 알고리즘을 알아야 한다.
  • a, b라는 두 노드를 연결한 간선이 있다고 해보자.
  • 만약 a, b의 부모 노드가 둘다 c라면 a와 b를 잇는 간선을 연결하면 사이클이 생겨버린다.
  • union-find
    • 크루스칼은 비용이 적은 간선을 찾는 그리디이기 때문에 간선 비용이 적은 순으로 정렬해둔다.
    • 모든 노드에 대한 부모 노드를 자기 자신으로 초기화한다.
    • 만약 두 부모 노드가 같지 않다면(초기에는 자기 자신이다.) 둘 중 하나의 노드 이름으로 부모명을 정한다.
      • A->B라면 A가 부모가 되는 식으로 구현했다.
    • 두 부모 노드가 같다면, 사이클이 형성되므로 건너뛴다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int V, E, a, b, c, P[10'002], ans;
tuple<int,int,int> edge[1'000'002];

int find(int x) {
	if(P[x] == x) return x;
	else return P[x] = find(P[x]);
}

void uni(int f, int t) {
	f = find(f);
	t = find(t);
	P[t] = f;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> V >> E;
	for(int i=0; i<E; i++){
		cin >> a >> b >> c;
		edge[i] = {c, a, b};
	}

	sort(edge, edge+E);
	for(int i=1; i<=V; i++) P[i] = i;


	for(int i=0; i<E; i++) {
		int f, t, cost;
		tie(cost, f, t) = edge[i];

		if(find(f) != find(t)) {
			uni(f, t);
			ans += cost;
		}
	}

	cout << ans;

	return 0;
}