[백준] 1647번 - 도시 분할 계획

문제 >

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

 

입력 >

첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.

출력 >

첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.

 

해결방법 > 

두 개의 최소신장 비용 트리를 만드는 문제다. 크루스칼 알고리즘을 사용했다.

 

주어진 간선을 n-1개로 연결했을 때, 하나의 그래프가 만들어진다.

 

주어진 간선을 n-2개 사용하면, 두개의 그래프가 만들어진다.

 

[JAVA]

package programmers;

import java.util.*;
import java.io.*;

public class BOJ_1647 {
	static int[] p;
	
	public static int find(int x) {
		if(x == p[x]) return x;
		return find(p[x]);
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x < y) p[y] = x;
		else p[x] = y;
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(tk.nextToken());
		int m = Integer.parseInt(tk.nextToken());
		int[][] c = new int[m][3];
		int cost = 0;
		p = new int[n + 1];
		
		for(int i = 1; i <= n; i++) p[i] = i;
		
		
		for(int i = 0; i < m; i++) {
			tk = new StringTokenizer(br.readLine());
			for(int j = 0; j < 3; j++) {
				c[i][j] = Integer.parseInt(tk.nextToken());
			}
		}
		
		Arrays.sort(c, new Comparator<int[]>() {
			@Override
			public int compare(int[] cmp1, int[] cmp2) {
				if(cmp1[2] > cmp2[2]) return 1;
				else if(cmp1[2] < cmp2[2]) return -1;
				else return 0;
			}
		});
		
		for(int i = 0; i < c.length; i++) {
			if(find(c[i][0]) != find(c[i][1])){
				cost += c[i][2];
				union(c[i][0], c[i][1]);
				n--;
				if(n <= 2) break;
			}
		}
		
		System.out.println(cost);
	}
}