요약
- 길의 길이 수 만큼 비용이 듦
- 가로등이 켜진 길로만 각 도시로 왕래 할 수 있음
- 최대 절약 액수 구하기
입력은 여러 개의 테스트 케이스로 구분되어 있다.
각 테스트 케이스의 첫째 줄에는 집의 수 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개 주어진다.
각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.
크루스칼 알고리즘을 사용하여 최소 신장(스패닝) 트리를 이용하면 된다.
단, 최대 절약 비용을 구하는 것이기 때문에 전체 비용에서 최소 비용을 뺀 결과를 출력해야 한다.
또한, 여러개의 테스트 케이스가 주어지기 때문에 while 반복문을 사용하여 m==0, n==0 일 때 반복문을 빠져나오게 해야한다.
처음에 total 과 최소비용을 멤버변수(전역?변수) 로 선언하여 풀다보니 문제를 계속 틀렸다. 이유는 여러개의 테스트 케이스를 생각을 안했기 때문인데, while문 안에 total과 최소비용을 계속 초기화 해줘야 하며, ArrayList로 선언한 edges 역시 마지막에 clear()를 해줘야 한다.
import java.util.*;
class Edge implements Comparable<Edge> {
private int distance;
private int nodeA;
private int nodeB;
public Edge(int distance, int nodeA, int nodeB) {
this.distance = distance;
this.nodeA = nodeA;
this.nodeB = nodeB;
}
public int getDistance() {
return this.distance;
}
public int getNodeA() {
return this.nodeA;
}
public int getNodeB() {
return this.nodeB;
}
@Override
public int compareTo(Edge o) {
if (this.distance < o.distance) {
return -1;
}
return 1;
}
}
public class Main {
// 집의 수(m) , 길의 수(n)
public static int m, n;
public static int[] parent = new int[200001];
public static ArrayList<Edge> edges = new ArrayList<Edge>();
public static int findParent(int x) {
if (x == parent[x])
return x;
return parent[x] = findParent(parent[x]);
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b)
parent[b] = a;
else
parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int result = 0, total = 0;
m = sc.nextInt();
n = sc.nextInt();
if (m == 0 && n == 0) {
break;
}
for (int i = 1; i <= m; i++) {
parent[i] = i;
}
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
total += z;
edges.add(new Edge(z, x, y));
}
Collections.sort(edges);
for (int i = 0; i < edges.size(); i++) {
int cost = edges.get(i).getDistance();
int a = edges.get(i).getNodeA();
int b = edges.get(i).getNodeB();
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
System.out.println(total - result);
edges.clear();
}
}
}