백준 1647. 도시 분할 계획

도시 분할 계획

 

---

Problem?

문제.

 

Solution

최소 스패닝 트리를 만든 후 가장 큰 cost를 가진 값을 빼면 해결되는 간단한 문제.

크루스칼(kruskal Algorithm)을 사용했다.

 

가정 simpleFind() : 부모 찾기 simpleUnion() : 노드 이어주기   graph : input parent : 부모 노드 유지

Code

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

#define MAX 100000 + 1

int N, M, ans = 0;
int parent[MAX];
vector<pair<int, pair<int, int>>> graph;

int simpleFind(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = simpleFind(parent[x]);
}

void simpleUnion(int x, int y) {
	int x_parent = simpleFind(x);
	int y_parent = simpleFind(y);
	if (x_parent != y_parent)
		parent[x_parent] = y_parent;
}

int main() {
	// input
	int start_pos, end_pos, weight;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &start_pos, &end_pos, &weight);
		graph.push_back({ weight, {start_pos, end_pos} });
	}

	// solution
	int max_value = 0;
	sort(graph.begin(), graph.end());
	for (int i = 1; i <= N; i++)
		parent[i] = i;
	for (int i = 0; i < M; i++) {
		if (simpleFind(graph[i].second.first) != simpleFind(graph[i].second.second)) {
			simpleUnion(graph[i].second.first, graph[i].second.second);
			ans += graph[i].first;
			if (graph[i].first > max_value)
				max_value = graph[i].first;
		}
	}
	ans -= max_value;

	// output
	cout << ans << "\n";

	return 0;
}

 

---

크루스칼 알고리즘을 이용한 최소 스패닝 트리 문제.