문제

요약

• 길의 길이 수 만큼 비용이 듦
• 가로등이 켜진 길로만 각 도시로 왕래 할 수 있음
• 최대 절약 액수 구하기

입력

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

각 테스트 케이스의 첫째 줄에는 집의 수 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();
		}
	}

}