[KOITP] 고속도로 건설

출    처 : http://koitp.org/problem/SDS_PRO_10_4/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	724	211 (29%)	156

문제

S 왕국의 새로운 정부는 모든 도시를 잇는 고속도로를 건설하려 한다. 그러나 비싼 비용의 문제에 부딪혀, 정부는 최소 비용으로 모든 도시 간을 이동할 수 있게 하고 싶어한다. 또한 하나의 제약이 더 있는데, 언덕 등을 깎지 않는 친환경 건설을 위해 어떤 도시끼리는 직접 도로를 이을 수 없다.

도로 후보의 목록이 주어질 때, 정부를 도와 모든 도시 간을 잇는 고속도로를 건설하는 최소 비용을 알아내자.

입력

첫 번째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 50,000)

두 번째 줄에 도로 후보의 수 M이 주어진다. (1 ≤ M ≤ 200,000)

세 번째 줄부터 M개의 줄에 걸쳐 각 도로 후보의 정보 s, e, c가 주어진다. s와 e는 도로 후보가 잇는 각 도시의 번호이고, c는 그 도로를 건설하는데 드는 비용이다. (1 ≤ s, e ≤ N, 1 ≤ c ≤ 10,000)

항상 모든 도시를 잇는 고속도로를 건설할 수 있는 입력만 주어진다.

출력

첫 번째 줄에 모든 도시를 잇는 고속도로를 건설하는데 드는 최소 비용을 출력한다.

힌트

예제 입력

5
8
1 2 4
1 3 9
1 4 21
2 3 8
2 4 17
3 4 16
5 2 20
5 4 30

예제 출력

48

< Comment >

 최소신장트리(MST) 로 푸는 문제라고 듣고 풀었음에도 유니온 파인드를 잘못 구현해서 꽤 시간이 걸렸습니다. Kruskal 알고리즘을 이용하여 풀이하였는데, 기본 컨셉은 코스트별로 모두 정렬한 뒤에, 앞에서부터 경로가 이어져있지 않을 경우를 유니온 파인드로 체크해, 경로가 이어져 있지 않을 경우에만 코스트를 더해주는 방식이었습니다. 기본적으로 앞의 것과 같은 그룹이 되면 사이클이 생기게되어, 사이클이 생기지 않는 경우보다 무조건 코스트가 높아지기 때문입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;


public class MST {
	
	public static int N = 0;
	public static int M = 0;
	
	public static ArrayList<Road> arr = null;
	public static int unionFind[] = null;
	
	public static class Road {
		
		int from = 0;
		int to = 0;
		int coast = 0;
		
		public Road(int from, int to, int coast) {
			this.from = from;
			this.to = to;
			this.coast = coast;
		}
		
		public int getFrom() {
			return this.from;
		}
		
		public int getCoast() {
			return this.coast;
		}
		
		public int getTo() {
			return this.to;
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		arr = new ArrayList<>();
		unionFind = new int[N + 1];
		for (int i = 1 ; i <= N ; i++) {
			unionFind[i] = i;
		}
		
		StringTokenizer st = null;
		int s, e, c;
		for (int i = 0 ; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			
			arr.add(new Road(s, e, c));
			arr.add(new Road(e, s, c));
		}
			
		Collections.sort(arr, new Comparator<Road>() {

			@Override
			public int compare(Road arg0, Road arg1) {
				if (arg0.getCoast() < arg1.getCoast())			return -1;
				else if (arg0.getCoast() == arg1.getCoast())	return 0;
				else											return 1;
			}
		});
		
		int coastSum = 0;
		for (Road road : arr) {
			
			int from = road.getFrom();
			int to = road.getTo();
			
			if (find(from) != find(to)) {
				union(from, to);
				coastSum += road.getCoast();
			}
		}
		
		bw.write("" + coastSum);
		bw.flush();
		bw.close();
	}
	
	public static void union(int num1, int num2) {
		int root1 = find(num1);
		int root2 = find(num2);
		unionFind[root2] = root1;
	}
	
	public static int find(int num) {
		if (unionFind[num] == num)	return num;
		return unionFind[num] = find(unionFind[num]);
	}

}