[백준] 6497번 전력난 C++ 코드

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int m, n, x, y, z, lst[200003], cnt, res, total;
vector<pair<int, pair<int, int>>> adj;

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

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x > y) lst[x] = y;
	else lst[y] = x;
}

bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
	return a.first < b.first;
}

void CLEAR() {
	adj.clear();
	res = 0;
	cnt = 0;
	total = 0;
	for (int i = 0; i < m; i++) lst[i] = i;
}

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	FASTIO();
	while(1) {
		cin >> m >> n;
		if (m == 0 && n == 0) break;
		CLEAR();
		for (int i = 0; i < n; i++) {
			cin >> x >> y >> z;
			total += z;
			adj.push_back({ z, {x, y} });
		}
		sort(adj.begin(), adj.end(), cmp);
		for (int i = 0; i < adj.size(); i++) {
			if (cnt == (m - 1)) break;
			int from = adj[i].second.first;
			int to = adj[i].second.second;
			int cost = adj[i].first;
			if (find(from) != find(to)) {
				merge(from, to);
				res += cost;
				cnt++;
			}
		}
		cout << (total - res) << '\n';
	}
	return 0;
}

풀이

도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다는 조건을 만족하면서 절약할 수 있는 최대 액수를 구해야 하는 문제다. 절약할 수 있는 최대 액수를 구하는 것은 전체 비용 - 연결 비용으로 구할 수 있으며, 이때 연결비용이 최소일 때 절약할 수 있는 최대 액수가 된다. 따라서 최소스패닝트리를 이용해 비용을 구하고 전체 비용에서 연결에 필요한 비용을 빼주는 방식으로 해결했다.

 

CLEAR 함수에는 전역으로 선언한 벡터와 변수들을 초기화 해주었다. find와 merge함수는 최소스패닝트리를 위해 구현해둔 유니온파인드 함수들이다. cmp는 벡터에 저장된 값을 비용을 기준으로 정렬하기 위해 만들었다.