백준 JAVA 1197번 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

최소 스패닝 트리(MST)의 가장 기본적인 문제라고 할 수 있다.

 

find를 통하여 부모를 찾고, union을 통하여 부모가 다를 경우 합치는 방식이다.

 

 

 

---

 

import java.util.*;

class Node implements Comparable<Node>{
    int start, end, weight;

    public Node(int start, int end, int weight){
        this.start=start;
        this.end=end;
        this.weight=weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight-o.weight;
    }
}
public class Main {
    static int [] parent;
    static PriorityQueue<Node> pq;

    static int n, k, start, end;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        k=sc.nextInt();
        parent= new int[n+1];
        pq= new PriorityQueue<>();
        for(int i=1; i<=n; i++){
            parent[i]=i;
        }
        for(int i=0; i<k; i++){
            int a= sc.nextInt();
            int b= sc.nextInt();
            int c=sc.nextInt();
            pq.add(new Node(a,b,c));
        }
        System.out.println(solve());
    }

    private static int solve() {
        int sum=0;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            int parentS = find(node.start);
            int parentE = find(node.end);
            if(parentS!=parentE){
                Union(parentS,parentE);
                sum+=node.weight;
            }
        }
        return sum;
    }

    private static int find(int x){
        if(parent[x]==x){
            return x;
        }
        else{
            return parent[x]=find(parent[x]);
        }
    }
    private static void Union(int a, int b){
        a=find(a);
    	b=find(b);
        if(a!=b){
        	parent[b]=a;
        }
    }
}