백준 1197번: 최소 스패닝 트리

[문제 링크]

1197번: 최소 스패닝 트리

---

최소 스패닝 트리를 구하는 알고리즘인 크루스칼 알고리즘을 사용하여 간단히 풀 수 있는 문제였다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class OptimizedDisjoinSet {
	vector<int> parent, rank;

public:
	OptimizedDisjoinSet(int n) : parent(n), rank(n, 1)
	{
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	int find(int u)
	{
		if (u == parent[u]) return u; //자기 자신을 가리키면 뿌리노드임
		return parent[u] = find(parent[u]); // 위에 부모노드가 있다면 재귀호출
	}

	void merge(int u, int v)
	{
		u = find(u); v = find(v);
		if (u == v) return; // 뿌리노드가 서로 같다면 걸러낸다

		// rank[u]의 높이가 더 높다면 rank[u]랑 rank[v]를 바꾼다
		if (rank[u] > rank[v]) swap(u, v);

		// 이제 무조건 rank[u]의 높이가 더 낮으므로 u를 v의 자식으로 넣는다
		parent[u] = v;

		// rank[u]와 rank[v]의 높이가 같다면 rank[v] 높이를 1 증가시킨다.
		if (rank[u] == rank[v]) ++rank[v];
	}
};

const int MAX_V = 10001;
int V, E;
vector<pair<int, int>> adj[MAX_V];

int kruskal()
{
	vector<pair<int, pair<int, int>>> edges;
	for (int u = 1; u <= V; u++)
		for (int i = 0; i < adj[u].size(); i++)
		{
			int v = adj[u][i].first;
			int cost = adj[u][i].second;

			edges.push_back({ cost, {u, v} });
		}

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

	OptimizedDisjoinSet sets(V+1);
	int ret = 0;

	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 (sets.find(u) == sets.find(v)) continue;

		sets.merge(u, v);
		ret += cost;
	}

	return ret;
}

int main(void) {
	cin >> V >> E;

	for (int i = 0; i < E; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		adj[A].push_back({ B, C });
	}

	cout << kruskal() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 164 day