문제
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.
그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.
위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.
입력
입력은 여러 개의 테스트 케이스로 구분되어 있다.
각 테스트 케이스의 첫째 줄에는 집의 수 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개 주어진다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.
예제 입력 1
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0예제 출력 1
51풀이 및 해설(풀이 참고)
출력값: 절약할 수 있는 최대 비용
▶︎ 크루스칼 알고리즘(최소 신장 트리 + 유니온파인드) 이용
1. 가중치(거리)를 오름차순 정렬
2. 맨 앞부터 연결되어있는 도시 정보를 꺼내 사이클을 이루는지 확인(m-1개 선택될 때까지 수행)
2-1. 선택된 도시의 부모 정점 찾기 → Find 이용
2-2. 두 도시의 부모 정점이 동일하면 사이클을 이루는 것! → 해당 길 선택 X
2-3. 두 도시의 부모 정점이 다르면 해당 길 선택 후, 도시 연결 → Union 이용
1) [0,3] 확인 → 길 선택
2) [2,4] 확인 → 길 선택
3) [3,5] 확인 → 길 선택
4) [0,1] 확인 → 길 선택
5) [1,4] 확인 → 길 선택
6) [1,2] 확인 → 길 X
7) [4,5] 확인 → 길 X
8) [1,3] 확인 → 길 X
9) [4,6] 확인 → 길 선택
Code
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const INF = Number.MAX_SAFE_INTEGER;
let line = 0;
let answer = '';
const Find = (x, parentNode) => {
if (x === parentNode[x]) return x;
else return (parentNode[x] = Find(parentNode[x], parentNode));
};
while (true) {
const [m, n] = input[line++].split(' ').map(Number); // m: 집의 수, n: 길의 수
if (m === 0 && n === 0) break; // 입력 끝인 경우 테스트케이스 종료
let totalCost = 0; // 도시의 기존 전력 비용
const parentNode = Array.from({ length: m }, (_, idx) => idx); // 부모 정점 배열(초기에는 본인 정점 넣기)
const city = []; // 연결되어 있는 도시 정보
for (let i = 0; i < n; i++) {
const [x, y, z] = input[line++].split(' ').map(Number); // x번 집과 y번 집 사이 거리가 z미터
totalCost += z;
city.push({ cost: z, node: [x, y] });
}
city.sort((a, b) => a.cost - b.cost || a.node[0] - b.node[0]); // 연결되어 있는 도시 정보 가중치(거리) 기준 오름차순 정렬
let selectCost = 0; // 선택된 거리의 비용
let selectCnt = 0; // 선택된 거리 개수
for (const c of city) {
const a = Find(c.node[0], parentNode);
const b = Find(c.node[1], parentNode);
if (a === b) continue; // 사이클 생성됨 -> 해당 길 선택 X
// 두 집 길 연결 시키기
parentNode[b] = a;
selectCost += c.cost;
selectCnt++;
if (selectCnt === m - 1) break; // 선택된 간선의 수가 m-1이면 종료
}
answer += totalCost - selectCost + '\n';
}
console.log(answer.trimEnd());