<Algorithm> 52. 1922번 네트워크 연결

1. 1922번 네트워크 연결 

• 기본 MST 문제,  정점 수 - 1 개의 간선으로 모든 정점이 연결 되는 지(최저비용으로 연결) 문제는 모두 MST 알고리즘을 사용하면 된다. 

• Prim 알고리즘이 약 180ms 정도 빨랐다. ( Prim O( Edge log Vertex) , Kruskal O( Edge log Edge )

Prim 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main{
    
    static boolean[] visited;
    static int[] dist;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));        
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine())+1;
        int M = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] aLists = new ArrayList[N];
        visited = new boolean[N];
        dist = new int[N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        for(int i = 0 ; i < N; i ++) {
            aLists[i] = new ArrayList<>();
        }
        for(int i = 0; i < M ; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
 
            aLists[a].add(new Edge(b, w));
            aLists[b].add(new Edge(a, w));            
        }
        
        prim(aLists);
        
        int ans = 0;
 
        for(int i = 1; i < N ; i++) {
            ans += dist[i];
        }
        System.out.println(ans);
    }
    public static void prim(ArrayList<Edge>[] aLists) {
        int start = 1;
        dist[start] = 0;
        
        PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        
        pq.add(new Edge(start, dist[start]));
        
        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            int vertex = edge.vertex;
            
            if(visited[vertex]) continue;
            visited[vertex] = true;
            
            for(Edge e : aLists[vertex]) {
                if(!visited[e.vertex]) {
                    int destination = e.vertex;
                    int weight = e.weight;
                    
                    if(weight < dist[destination]) {
                        dist[destination] = weight;
                        pq.add(new Edge(destination, dist[destination]));
                    }
                }
            }
            
        }
    }
}
class Edge{
    int vertex, weight;
 
    public Edge(int vertex, int weight) {
        super();
        this.vertex = vertex;
        this.weight = weight;
    }
    
}

   

 

Kruskal

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main{
    
    private static int find(int i) {
        if(parent[i] != i) {
            return find(parent[i]);
        }else
            return parent[i];
    }
    private static boolean union(int i, int j) {
        int iroot = find(i);
        int jroot = find(j);
    
        if(iroot == jroot) return false;
        
        parent[jroot] = iroot;
        return true;
        
    }
    public static int[] parent;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
            BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken())+1;
            int M = Integer.parseInt(st.nextToken());
            StringTokenizer st;
            int N = Integer.parseInt(br.readLine())+1;
            int M = Integer.parseInt(br.readLine());
            parent = new int[N];
            for(int i = 0; i < N ; i ++) parent[i] = i;
            
            
            PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    // TODO Auto-generated method stub
                    return o1.w - o2.w;
                }
            });
            
            for(int i = 0; i < M ; i ++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int w = Integer.parseInt(st.nextToken());
                pq.add(new Node(a, b, w));
            }
            
            int total = 0;
            
            while(!pq.isEmpty()) {
                
                Node node = pq.poll();
                
                if(union(node.a,node.b)) {
                    total += node.w;
                }
            }
            
            System.out.println(total);
    }
    
    
}    
 
class Node{
    int a,b,w;
 
    public Node(int a, int b, int w) {
        super();
        this.a = a;
        this.b = b;
        this.w = w;
    }
    
}