[BOJ] 1922. 네트워크 연결

최소신장트리를 찾는 MST문제이다.

이문제를 해결함에 있어 간선중심의 Kruskal 알고리즘 대신, PriorityQueue를 활용한 Prim 알고리즘을 사용하였다. Edge라는 클래스를 만들어서 weight를 기준으로 빠른 값이 올수있게 최소힙을 사용하는 PriorityQueue를 사용하였다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_1922_네트워크연결 {
    
    static int V,E;
    static List<Edge>[] map;
    
    static boolean[] visit;
    static int d[];
    
    static class Edge implements Comparable<Edge>{
        int point,weight;
        Edge(int p,int w){
            point=p;weight=w;
        }
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(weight, o.weight);
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        V=Integer.parseInt(br.readLine());
        E=Integer.parseInt(br.readLine());
        
        map=new ArrayList[V];
        for(int i=0;i<V;i++)
            map[i]=new ArrayList<>();
        
        for(int i=0;i<E;i++) {
            st=new StringTokenizer(br.readLine());
            int v1=Integer.parseInt(st.nextToken())-1;
            int v2=Integer.parseInt(st.nextToken())-1;
            int w=Integer.parseInt(st.nextToken());
            if(v1!=v2) {
                map[v1].add(new Edge(v2, w));
                map[v2].add(new Edge(v1, w));
            }
        }
        
        d=new int[V];
        for(int i=0;i<V;i++) {
            d[i]=Integer.MAX_VALUE;
        }
        visit=new boolean[V];
        
        prim(0);
        
        int dis=0;
        for(int i=0;i<V;i++)
            dis+=d[i];
        
        System.out.println(dis);
        
    }
    static void prim(int begin) {
        d[begin]=0;
        
        PriorityQueue<Edge> pq=new PriorityQueue<>();
        pq.add(new Edge(begin, 0));
        
        
        while(!pq.isEmpty()) {
            Edge e= pq.poll();
            int start=e.point;
            
            if(visit[start]==true)
                continue;
            
            for(Edge next :map[start] ) {
                int dest=next.point;
                int weight=next.weight;
                
                if(visit[dest]==false && d[dest]>weight) {
                    d[dest]=weight;
                    pq.add(new Edge(dest, weight));
                }
            }
            
            visit[start]=true;
            
        }
        
    }
}