swea 3124 최소 스패닝 트리 //Kruskal 알고리즘

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb 

SW Expert Academy

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_3124_유동훈 {
	
	

	static class Edge implements Comparable<Edge>
	{
		int from,to,weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return this.weight-o.weight;
		}
		//싼거부터 나오게 정렬
		
	}
	
	static int[] parents;
	static int V,E;
	static Edge[] edgeList;
	
	/**
	 * 크기가 1인 서로조 집합 생성
	 * 모든 노드가 자신을 부모로 하는 집합으로 만들기
	 */
	static void make()
	{
		parents=new int[V+1];
		for(int i=0;i<=V;++i)
		{
			parents[i]=i;
		}
	}
	
	/**
	 * x의 대표자 찾기
	 * @param x
	 * @return
	 */
	public static int find(int x) {
		//x의 부모== x->내가 루트임.
		if (parents[x] == x) 
		{
			return x;
		}
		//아니면 내 부모의 부모를 찾아라
		//반복
		//else 
		{
			return parents[x]=find(parents[x]);
			//우리의 대표자를 나의 부모로 : path compression
		}
	}
 
	/**
	 * 
	 * @param a
	 * @param b
	 * (A를 B에 연결)
	 * A의 루트노드를 B의 루트노드에 연결
	 * (A위에 B를 부모로)
	 * 
	 * @return 유니언 성공시 true
	 */
	public static boolean union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
 
		if (rootA == rootB) return false;
		
		//B의 루트노드를 A의 루트노드에 연결
		parents[rootB] = rootA;
		return true;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T=Integer.parseInt(br.readLine());
		
		for(int t=1;t<=T;++t)
		{
			StringTokenizer 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());
				edgeList[i]=new Edge(Integer.parseInt(st.nextToken())
						,Integer.parseInt(st.nextToken()),
						Integer.parseInt(st.nextToken()));
			}
			//입력끝!
			
			make();
			//1. 정렬
			Arrays.sort(edgeList);
			
			long result=0L;	//최소 가중치==정답
			int count=0;
			
			//2.정렬되있음 -> 앞부터 연결하면됨
			for(Edge edge:edgeList)
			{
				if(union(edge.from,edge.to))
				{
					result=result+edge.weight;
					
					//모두연결되면 끝내기
					if(++count==V-1) 
					{
						break;
					}
				}
			}
			
			System.out.println("#"+t+" "+result);
		}
		

	}

}