👓 문제 설명
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.
그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.
위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.
💣 제한 사항
- 입력은 여러 개의 테스트 케이스로 구분되어 있다.
- 각 테스트 케이스의 첫째 줄에는 집의 수 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)의 문제이다.
입력으로 시작 정점, 도착 정점, 간선의 비용이 주어졌다.
이를 바로 이용하고자
크루스칼 알고리즘을 적용했다.
문제에서는 절약할 수 있는 최대 비용을 요구했다.
따라서 현재 사용되고 있는 (입력으로 주어진 모든) 비용을 구해놓은 뒤 MST를 형성했을 때의 비용을 빼면 절약할 수 있는 최대 비용을 구할 수 있다.
크루스칼 알고리즘
1. sort (가중치 낮은 순)
2. Union-Find
3. for문 진행
정점과 간선의 정보를 가중치가 낮은 순서부터 정렬하고 for문을 통해 유니온 파인드를 진행한다.
이 때, find() 함수를 통해 서로의 그룹이 같은지 판단한다 (사이클 형성이 되는지)
서로의 그룹이 같지 않으면 유니온을 진행한다.
만약 현재 그룹 형성 (간선 연결)이 n-1개라면,
MST를 형성했으므로 종료한다.
🚈 풀이
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// 집의 수 m, 길의 수 n
int m, n;
int parent[200001];
int total;
struct node {
int s, e, w;
};
vector<node>nodes;
// 전체 비용을 더한 후 최소 비용으로 연결한 값을 빼면
// 절약할 수 있는 최대 치를 구할 수 있음
bool cmp(node a, node b) {
return a.w < b.w;
}
void input() {
for (int i = 0; i < n; i++) {
int s, e, w;
cin >> s >> e >> w;
total += w;
node a = { s,e,w };
node b = { e,s,w };
nodes.push_back(a);
nodes.push_back(b);
}
sort(nodes.begin(), nodes.end(), cmp);
}
void init() {
total = 0;
nodes.clear();
for (int i = 0; i < m; i++) {
parent[i] = i;
}
}
int find(int tar) {
if (tar == parent[tar])return tar;
int ret = find(parent[tar]);
parent[tar] = ret;
return ret;
}
void setUnion(int a, int b) {
int t1 = find(a);
int t2 = find(b);
if (t1 == t2)return;
parent[t2] = t1;
}
void Kruskal() {
int target = n - 1;
int result = 0;
int selectCount = 0;
for (auto p : nodes) {
int s = p.s;
int e = p.e;
int w = p.w;
if (find(s) == find(e))continue;
setUnion(s, e);
result += w;
selectCount++;
if (selectCount == target)break;
}
cout << total - result << "\n";
}
int main() {
while (1) {
cin >> m >> n;
if (m == 0 && n == 0)break;
init();
input();
Kruskal();
}
return 0;
}