백준 1647번 도시 분할 계획 C++ MST, 최소 신장 트리

리뷰

MST를 구하고 그 과정에서 가장 큰 가중치를 가진 간선의 가중치를 빼주는 문제

 

문제 풀이

1. n의 최대값은 10만이므로 100001 크기의 nodes 배열을 초기화 해준다.
2. n과 m 값을 받고 m만큼의 가중치와 노드 정보를 edges 벡터에 추가해 준 뒤 오름차순으로 정렬해 준다.
3. Union-Find를 통해 최소 신장 트리를 만들어 주고, 트리를 만들며 각 가중치를 더해주며 가장 큰 가중치를 구해준다.
4. 가중치의 합에서 가장 큰 가중치를 뺀 값을 출력해 준다.

 

참고 사항

간선의 유지비가 최대 1000이고, 간선은 최대 100만개 이므로 int 범위 내에서 문제를 해결할 수 있다.

 

 

정답 코드

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

using namespace std;

int nodes[100001];
int n, m;

vector<tuple<int, int, int>> lst;

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int rootA = Find(a);
	int rootB = Find(b);
	if (rootA == rootB) return;
	nodes[rootB] = rootA;
}

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

	cin >> n >> m;

	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		edges.push_back({ c, a, b });
	}
	sort(edges.begin(), edges.end());

	for (int i = 1; i <= n; i++) {
		nodes[i] = i;
	}

	int sum = 0, max_val = 0;
	for (int i = 0; i < m; i++) {
		tuple<int, int, int> cur = edges[i];
		if (Find(get<1>(cur)) == Find(get<2>(cur))) continue;
		Union(get<1>(cur), get<2>(cur));
		sum += get<0>(cur);
		max_val = max(max_val, get<0>(cur));
	}
	cout << sum - max_val;
}