[BOJ] 백준 [1197] 최소 스패닝 트리 JAVA

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

문제

풀이

크루스칼 알고리즘을 이용한 최소 신장트리를 구하는 문제이다.

Edge를 weight가 작은 순으로 Queue에 넣은 뒤 ( priorityQueue사용)

parent 배열의 크기를 정점의 갯수만큼 정해주고 ,

union연산으로 disjointSet을 만들어가면서 가중치를 더하는 식으로 하면 된다.

 

 
import java.util.*;
import java.io.*;
 
public class Main{
    static int V,E,sum;
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        V = Integer.parseInt(input[0]); E = Integer.parseInt(input[1]);
        for(int i=0;i<E;i++){
            input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int weight = Integer.parseInt(input[2]);
            pq.add(new Edge(start,end,weight));
        }
        parent = new int[V+1];
        for(int i=1;i<=V;i++)
            parent[i] = i;
        while(!pq.isEmpty()){
            Edge poll = pq.poll();
            int s = poll.start;
            int e = poll.end;
            int w = poll.weight;
 
            if(find(s)==find(e))
                continue;
            union(s,e);
            sum+=w;
        }
        System.out.println(sum);
    }
    static int find(int x){
        if(x == parent[x])
            return x;
        parent[x] = find(parent[x]);
        return parent[x];
    }
    static void union(int x,int y){
        int xRoot = find(x);
        int yRoot = find(y);
        if(xRoot != yRoot)
            parent[yRoot] = x;
    }
    static class Edge implements Comparable<Edge>{
        int start,end;
        int weight;
        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            return this.weight-o.weight;
        }
    }
}