[JAVA/자바 SWEA 3124] 최소 스패닝 트리

풀이

* Kruskal 알고리즘 - 인접 리스트 사용

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

//Kruskal
// 정점과 간선이 크므로 edgelist로 풀어아야함
// 가중치 값이 1,000,000이 누적되면 int 범위 넘으므로, result를 long 타입

public class Solution{

	static int[] parents;
	static int V,E;
	static Edge[] edgeList;
	
	static class Edge implements Comparable<Edge>{
		int start,end,weight;

		public Edge(int start, int end, int weight) {
			super();
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.weight, o.weight);
		}
		
	
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		
		int t=Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=t;tc++) {
			st=new StringTokenizer(br.readLine()," ");
			V=Integer.parseInt(st.nextToken());
			E=Integer.parseInt(st.nextToken());
			
			edgeList=new Edge[E];
			
			for(int i=0;i<E;i++) {
				st=new StringTokenizer(br.readLine()," ");
				int start=Integer.parseInt(st.nextToken())-1;
				int end=Integer.parseInt(st.nextToken())-1;
				int weight=Integer.parseInt(st.nextToken());
				edgeList[i]=new Edge(start, end, weight);
			}
			Arrays.sort(edgeList);
			
			make();
			
			int cnt=0 ;
			long result=0;
			for(Edge edge: edgeList) {
				if(union(edge.start, edge.end)) {
					result+=edge.weight;
					if(++cnt==V-1) break;
				}
			}
			sb.append("#").append(tc).append(" ").append(result).append("\n");
		}
		System.out.println(sb);
	}

	private static boolean union(int a, int b) {
		// TODO Auto-generated method stub
		int aRoot=find(a);
		int bRoot=find(b);
		if(aRoot==bRoot)return false;
		
		parents[bRoot]=aRoot;
		return true;
	}

	private static int find(int a) {
		// TODO Auto-generated method stub
		if(a==parents[a]) return a;
		
		return parents[a]=find(parents[a]);
	}

	private static void make() {
		// TODO Auto-generated method stub
		parents=new int[V];
		
		for(int i=0; i<V;i++) {
			parents[i]=i;
		}
	}

}

 

* Prim - Priority Queue, 인접 리스트 사용

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

// prim
// priority queue와 edgelist edge(v,w)타입
//정점과 간선이 크므로 edgelist로 풀어아야함
//가중치 값이 1,000,000이 누적되면 int 범위 넘으므로, result를 long 타입

public class Solution_d4_최소스패닝트리_3124_서울_12반_정광균2{
	// 간선과 정점
	static int V,E;
	
	// pq와 edgelist에 넣을 값. (v,w) 
	static class Edge implements Comparable<Edge>{
		int v, w;

		Edge(int e, int v) {
			this.v = e;
			this.w = v;
		}
		
		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return this.w - o.w;
		}
	}
    public static void main(String[] args) throws Exception {
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		
		int t=Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=t;tc++) {
			st=new StringTokenizer(br.readLine()," ");
			V=Integer.parseInt(st.nextToken());
			E=Integer.parseInt(st.nextToken());
			boolean[] visited= new boolean[V];
			
			List<Edge>[] edgeList = new ArrayList[V];
			
			for(int i=0;i<V;i++) {
				edgeList[i] = new ArrayList<Edge>();
			}
			
			for(int i=0; i<E; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken())-1;
				int to = Integer.parseInt(st.nextToken())-1;
				int weight=Integer.parseInt(st.nextToken());
				
				// edgeList 출발idx에 목적idx와 가중치
				edgeList[from].add(new Edge(to,weight));
				edgeList[to].add(new Edge(from,weight));
			}
			
			//pq 선언. (v,w)로 넣어주고  w에 따라 정렬
			PriorityQueue<Edge> pq=new PriorityQueue<Edge>();
			
			// 가중치 더하다보면 int 넘어가므로 long
			long result=0;
			int cnt=0;
			//임의의 출발지.
			visited[0]=true;
			
			// 0과 연결된 간선들 pq에 넣어주기
			for(Edge e : edgeList[0]) {
				pq.add(e);
			}
			// pq에 가중치가 작은 간선들부터 탐색
			while(!pq.isEmpty()){
				Edge cur=pq.poll();
				
				if(visited[cur.v]) continue;
				// 가중치 더해주기
				result+=cur.w;  
				
				// 방문처리
				visited[cur.v]=true;
				
				//v-1 일때 완성
				if(cnt++ == V-1) break; 
				
				for(Edge e:edgeList[cur.v]) {
					// 방문한 정점 continue
					if(visited[e.v]) continue;
					// 방문 안했다면 pq넣어주기
					pq.add(e);
				}
			}
			sb.append("#").append(tc).append(" ").append(result).append("\n");
		}

        System.out.println(sb);
        br.close();
    }
}