[알고리즘] SW expert - 최소 스패닝 트리 java (Prim 풀이)

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

/*
 Node class를 만들어서 Node형 배열을 선언한다 
 Node class에는 인접 정점의 번호, 그 정점까지의 거리를 변수로 갖는다  
 
 */

public class swea최소스패닝트리_prim버전 {

	static class Node implements Comparable<Node>{
		int nodenum;
		int len;
		
		Node(int nodenum, int len){
			this.nodenum = nodenum;
			this.len = len;
		}

		@Override
		public int compareTo(Node o) {
			return this.len - o.len;
		}
	}
	
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			StringTokenizer ST = new StringTokenizer(br.readLine());
			int nodenum = Integer.parseInt(ST.nextToken());
			int edgenum = Integer.parseInt(ST.nextToken());
			
			ArrayList<Node>[] adnode = new ArrayList[nodenum+1];		//node 개수만큼 노드별 인접노드 배열 선언
			
			for(int i=0; i<=nodenum; i++) {
				adnode[i] = new ArrayList<>();
			}
			
			for(int i=0; i<edgenum; i++) {						//노드별 인접노드 작업 
				ST = new StringTokenizer(br.readLine());
				
				int from = Integer.parseInt(ST.nextToken());
				int to = Integer.parseInt(ST.nextToken());
				int weight = Integer.parseInt(ST.nextToken());
				
				adnode[from].add(new Node(to, weight));
				adnode[to].add(new Node(from, weight));
			}
			
			int visit[] = new int[nodenum+1];
			PriorityQueue<Node> pq = new PriorityQueue<>();
			
			
			int unioncnt = 0;
			long result = 0;
			pq.add(new Node(1, 0));
			
			while(!pq.isEmpty()) {
				
				Node nownode = pq.poll();
				
				if(visit[nownode.nodenum]==1)continue;
				
				
				visit[nownode.nodenum] = 1;
				result+=nownode.len;
				
				unioncnt++;
				if(unioncnt==nodenum)break;
				
				for(int k=0; k<adnode[nownode.nodenum].size(); k++) {
					Node adj = adnode[nownode.nodenum].get(k);
					if(visit[adj.nodenum]==1)continue;
					else pq.add(adj);
				}
			}
			
			System.out.println("#"+t+" "+result);
		}
		
	}

}