백준 1197번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 4

---

풀이

 문제 이름이 정답인 문제다. 최소 스패닝 트리(Minimum Spanning Tree, MST), 최소 신장 트리라고 하는 이 문제는 임의의 그래프가 주어졌을 때, 모든 정점을 최소한의 비용으로 모두 연결하는 알고리즘이다. MST를 구하는 알고리즘은 세가지가 있다. 프림, 솔린, 크루스칼 알고리즘이 있는데, 나는 유니온파인드 자료구조도 같이 공부할 겸 크루스칼을 공부한 상태이다. 크루스칼 알고리즘은 나중에 언젠가 정리하겠지만, 간단하게 설명하면 모든 정점을 유니온파인드 자료구조에서 루트노드인 상태, 그러니까 미연결상태로 둔 뒤, 간선의 가중치를 오름차순으로 정렬한다. 간선 정보들을 선형탐색하면서, 두 정점이 같은 집합이 아니라면 연결하고, 이미 같은 집합에 있다면 무시하는 방식으로 모든 정점을 연결한다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

typedef struct Disjoint_set{
	int* tree;
	Disjoint_set(int n) {
		tree = new int[n + 1];
		memset(tree, 0xff, sizeof(int) * (n + 1));
	}

	void merge(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return;
		tree[b] = a;
	}

	int find(int a) {
		if (tree[a] < 0) return a;
		return tree[a] = find(tree[a]);
	}

	~Disjoint_set() { delete[] tree; }
};

int v, e;
vector<tuple<int,int,int>> path;

void input() {
	cin >> v >> e;
	path.resize(e);
	for(auto& [d, a, b] : path) cin >> a >> b >> d;
}

void sol() {
	Disjoint_set ds(v);
	int edge = 0, answer = 0;

	sort(ALL(path));
	for(auto& [dist, st, ed] : path) {
		if (edge == v - 1) break;

		int rst = ds.find(st), red = ds.find(ed);
		if (rst + red == -2 || rst != red) {
			answer += dist;
			edge++;
			ds.merge(st, ed);
		}
	}
	cout << answer;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}