[Algorithm] 고속도로 건설

http://www.koitp.org/problem/SDS_PRO_10_4/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	710	202 (28%)	149

문제

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

>> prim kruskal 알고리즘

https://www.google.co.kr/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#newwindow=1&q=prim+kruskal+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
 
/*
예제 입력

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
 */

class Doro{
	int node, cost;

	public Doro(int node1, int cost) {
		super();
		this.node = node1;
		this.cost = cost;
	}

}
class source{
    public static void main(String[] args) 
            throws IOException 
    {
         
        InputStreamReader fr = new InputStreamReader(System.in);
//    	FileReader fr = new FileReader("D:\\dev\\worksspace\\Solution\\src\\source");
        BufferedReader br = new BufferedReader(fr);
        String s;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        while ((s=br.readLine())!=null) {
        	
        	int N = Integer.parseInt(s);
        	int M = Integer.parseInt(br.readLine());
        	
        	ArrayList<ArrayList<Doro>> arr = new ArrayList<ArrayList<Doro>>();
        	for (int i = 0; i <= N; i++) {
				arr.add(new ArrayList<Doro>());
			}
        	
        	int a,b,c;
        	for (int i = 0; i < M; i++) {
        		st = new StringTokenizer(br.readLine());
        		a = Integer.parseInt(st.nextToken());
        		b = Integer.parseInt(st.nextToken());
        		c = Integer.parseInt(st.nextToken());
        		arr.get(a).add(new Doro(b,c));
        		arr.get(b).add(new Doro(a,c));
			}
        	
        	//알고리즘 시작
        	int[] visit = new int[N+1]; // 방문했는지 여부
        	
        	PriorityQueue<Doro> pq = new PriorityQueue<Doro>(new Comparator<Doro>() {
				@Override
				public int compare(Doro o1, Doro o2) {
					return o1.cost-o2.cost;
				}
			});
        	
        	pq.add(new Doro(1,0));
        	ArrayList<Doro> tempP;
        	Doro d, d2;
        	int answer = 0;
        	
        	while (!pq.isEmpty()) {
				d = pq.poll();
				if(visit[d.node] == 1) continue;
				tempP = arr.get(d.node);
				visit[d.node] = 1;
				answer += d.cost;
				
				for (int i = 0; i < tempP.size(); i++) {
					d2 = tempP.get(i);
					if(visit[d2.node] == 0){
						pq.add(d2);
					}
				}
			}
        	
        	boolean exist = true;
        	for (int i = 1; i <= N; i++) {
				if(visit[i] == 0){
					exist = false;
					break;
				}
			}
        	
        	if(!exist) System.out.println(-1);
        	else
        		System.out.println(answer);
        }
    }
        	
}