[백준][1197]최소 스패닝 트리

/* 문제설명 */

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

 

 

 

---

 

 

 

/* 풀이방법 */

PRIM알고리즘을 사용해서 풀이했다.

https://jinniepark.tistory.com/46

[알고리즘 기본]PRIM 알고리즘

 

 

 

 

 

---

 

/* 해답코드 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//최소 스피닝 트리
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		ArrayList<Edge>[] adjList = new ArrayList[V+1];
		for(int i=1;i<=V;i++) {
			adjList[i] = new ArrayList<Edge>();
		}
		for(int i=0;i<E;i++) {
			st =new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adjList[s].add(new Edge(e,w));
			adjList[e].add(new Edge(s,w));
		}
		
		int[] min_edge = new int[V+1];
		Arrays.fill(min_edge, Integer.MAX_VALUE);
		boolean[] visited = new boolean[V+1];
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		q.add(new Edge(1,0));
		
		int cnt=0;
		while(!q.isEmpty()) {
			Edge edge = q.poll();
			if(visited[edge.n])continue;
			
			visited[edge.n]=true;
			min_edge[edge.n] = edge.dist;
			for(Edge next : adjList[edge.n]) {
					if(!visited[next.n]) {
						q.add(next);
				}
			}
			if(++cnt==V)break;
		}
		int sum=0;
		for(int i=1;i<=V;i++) {
			sum+=min_edge[i];
		}
		System.out.println(sum);
	}
}


class Edge implements Comparable<Edge>{
	int n;
	int dist;
	public Edge(int n, int dist) {
		super();
		this.n = n;
		this.dist = dist;
	}

	@Override
	public int compareTo(Edge o) {
		return Integer.compare(this.dist, o.dist);
	}
}