문제

풀이

1. 우선순위큐를 사용하여 크루스칼 알고리즘 구현
2. 유니온파인드를 통해서 연결된 노드를 한 그룹으로 묶어줬다.

코드

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

public class Main {

    static int[] group;
    static int groupCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int n=Integer.parseInt(br.readLine());
        int m=Integer.parseInt(br.readLine());
        group=new int[n+1];
        groupCnt=n;
        for(int i=1;i<n+1;i++)group[i]=i;
        PriorityQueue<Line> pq=new PriorityQueue<>();
        for(int i=0;i<m;i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            int c=Integer.parseInt(st.nextToken());
            pq.add(new Line(a,b,c));
        }

        int ans=0;
        while(!pq.isEmpty()){
            if(groupCnt==1)break;
            Line line=pq.poll();
            if(line.a==line.b)continue;
            boolean ret=union(line.a, line.b);
            if(ret)ans+=line.cost;
        }
        System.out.println(ans);
    }

    static int find(int x){
        if(x!=group[x]){
            group[x]=find(group[x]);
        }
        return group[x];
    }

    static boolean union(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b)return false;
        if(a<b)group[b]=a;
        else group[a]=b;
        groupCnt--;
        return true;
    }

    static class Line implements Comparable<Line>{
        int a,b,cost;

        public Line(int a, int b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        public int compareTo(Line o){
            return this.cost-o.cost;
        }
    }
}

#MST #유니온파인드