[C/C++] 백준 - 6497번 (전력난)

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

6497번: 전력난

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

 

집을 노드, 집 사이의 길을 간선이라고 할 때 간선의 길이를 최소화로 한다면 절약할 수 있는 최대 액수를 구할 수 있다. 즉 최소 스패닝 트리 알고리즘을 이용하여 이 문제를 해결할 수 있다. 나는 MST 알고리즘 중 크루스칼 알고리즘을 이용하여 이 문제를 해결하였다. 

 

1) 노드와 간선을 입력받으면서 모든 정보를 우선순위 큐에 넣었고, 간선의 비용을 모두 더해 총 비용을 구해주었다.

2) 크루스칼 알고리즘을 이용하여 최소 비용으로 모든 정점을 연결시켜주었다. V개의 정점을 연결하는 간선의 최소개수는  V-1개이므로 우선순위 큐에서 부모 노드가 다른 정점을 연결시켜줄 때마다 카운트 해주었고, V-1개의 간선 비용 합을 더하는 순간 반복문을 탈출하였다.

3) 1번에서 구한 모든 간선의 비용에서 2번에서 구한 최소 비용의 간선 길이를 빼주면 절약할 수 있는 최대 액수를 구할 수 있다.

#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 987654321
#define ENDL cout << endl
#define endl '\n'

using namespace std;;

struct cmp {
	bool operator()(pair<int, pair<int, int>> A, pair<int, pair<int, int>> B) {
		return A.first > B.first;
	}
};

int N, M;
vector<pair<int, int>> adj[200003];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, cmp> pq;
int parent[200003];
bool visited[200003];

void Init(int n) {
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		parent[i] = i;
	}
	while (!pq.empty()) pq.pop();
}

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

void Union(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	if (a < b) parent[b] = a;
	else parent[a] = b;
}

bool isSame(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	if (a == b) return true;
	return false;
}

int MST_algorithm(int n) {
	int edge = 0;
	int cnt = 0;
	while (!pq.empty()) {
		int node1 = pq.top().second.first;
		int node2 = pq.top().second.second;
		int cost = pq.top().first;
		pq.pop();

		if (!isSame(node1, node2)) {
			edge += cost;
			Union(node1, node2);
			cnt++;
		}
		if (cnt == n - 1) break;
	}
	return edge;
}

int main(){
	fastio;
	while (1) {
		cin >> N >> M;
		if (N == 0 && M == 0) break;
		Init(N);
		int total = 0;
		for (int i = 0; i < M; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			adj[a].push_back({ b, c });
			adj[b].push_back({ a,c });

			pq.push({ c, {a, b} });
			total += c;
		}
		int minV = MST_algorithm(N);
		cout << total - minV << endl;
	}

	return 0;
}