[백준 1922] 네트워크 연결(Java)

문제 링크 : https://www.acmicpc.net/problem/1922

이 문제는 최소 신장 트리를 이용하여 풀 수 있습니다. 모든 노드의 연결 비용을 최소로 하기 위한 문제의 경우 최소 신장 트리를 이용하여 풀 수 있기 때문에 우선순위 큐를 이용하여 최소 신장 트리를 구현하여 해결합니다.

다음은 코드입니다.

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

class Main{
    static int N,M;
    static PriorityQueue<Edge> queue = new PriorityQueue<>();
    static int[] parent;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        parent = new int[N+1];
        for(int i=1;i<=N;i++) parent[i] = i;

        for(int i=0;i<M;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            queue.add(new Edge(s,e,v));
        }

        int res = 0;
        while(!queue.isEmpty()){
            Edge curr = queue.poll();
            if(find(curr.s) != find(curr.e)){
                union(curr.s, curr.e);
                res += curr.v;
            }
        }
        System.out.println(res);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b) parent[b] = a;
    }

    static int find(int a){
        if(a == parent[a]) return a;
        else return parent[a] = find(parent[a]);
    }

    static class Edge implements Comparable<Edge>{
        int s;
        int e;
        int v;

        Edge(int s, int e, int v){
            this.s = s;
            this.e = e;
            this.v = v;
        }

        @Override
        public int compareTo(Edge o) {
            return this.v - o.v;
        }
    }
}