백준 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개 주어진다.

출력

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

예제 입력 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

풀이

전체 가로등 중에서 최소한의 가로등만 켜서 전력을 아껴야 하기 때문에, 최소 스패닝트리(MST)를 구해서, 전체 길의 길이 - MST를 구성하는 길의 길이 를 구하면 갑이 수해진다.

 

MST를 구하는데는 크루스칼 알고리즘을 이용하면 간단하게 해결이 가능한다.

1. edge 가중치를 오름차순으로 정렬한다.

2. 가장 작은 가중치의 edge부터 확인하여, 양 끝 점이 이미 연결되어있는지 확인 후 아니라면 이어준다.

3. 선택된 edge의 갯수가 전체 node - 1이면 종료한다.

 

마지막에 0 0 이 들어오기전까지 반복 꼭 체크

코드

package test6497;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int[] parent;
	static int M; // 집의 수
	static int N; // 길의 수
	static int[][] edges; // edge 입력

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);
		while (true) {

			M = sc.nextInt();
			N = sc.nextInt();

			if (M == 0 && N == 0) {
				return;
			}

			edges = new int[N][3];

			int total_cost = 0;
			for (int i = 0; i < N; i++) {
				edges[i][0] = sc.nextInt();
				edges[i][1] = sc.nextInt();
				edges[i][2] = sc.nextInt();

				total_cost += edges[i][2];
			}

			Arrays.sort(edges, (a, b) -> a[2] - b[2]); // 간선을 기준으로 오름차순으로 정렬

			parent = new int[M + 1];
			for (int i = 1; i <= M; i++) {
				parent[i] = i;
			}

			int min_cost = 0;
			int selected_cnt = 0;
			int i = 0;
			while (true) {
				if (find(edges[i][0]) != find(edges[i][1])) { // cycle이 아니면
					union(edges[i][0], edges[i][1]);
					min_cost += edges[i][2];
					selected_cnt++;
				}
				if (selected_cnt == M - 1) {
					break;
				}
				i++;
			}
			System.out.println(total_cost - min_cost);
		}
	}

	public static int find(int idx) {
		if (parent[idx] == idx) {
			return idx;
		}
		parent[idx] = find(parent[idx]);
		return parent[idx];
	}

	public static void union(int a, int b) {
		int parent_of_a = find(a);
		parent[parent_of_a] = b; // 주의,,, a의 parent를 b로 바꿔야 a가 b랑 합쳐지는 것!
	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}

	}
}

 

참고

크루스칼 알고리즘

union-find 알고리즘