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

---

제목 그래도 가장 기본적인 최소 스패닝 트리 문제였다.

크루스칼 알고리즘을 통해 문제를 풀었다.

크루스칼 알고리즘은 간선의 가중치가 가장 작은 것을 고르고 사이클이 생기지 않는 노드만 방문 하는 것이다.

결국 두 가지 핵심으로 나눌 수 있다.

하나는 가중치가 작은 것을 고르기

다른 하나는 어떻게 사이클이 생기지 않게 하기이다.

 

가중치가 작은 것 고르기는 우선순위큐에 간선을 기준으로 넣어주면 된다. 그럼 저절로 가중치가 작은 순서대로 저장할 수 있다.

 

사이클이 생기지 않게 하기는 union-find알고리즘을 이용하면 된다. 노드의 최종 부모가 누구인지를 확인하는 방법인데 시작노드와 끝노드의 최종 부모가 같으면 사이클이 생기는 것이다.

 

코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class minimum_spanning_tree {
    static class edge implements Comparable<edge>{
        int s,e,v;

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

        @Override
        public int compareTo(edge o) {
            return o.v>=this.v ? -1:1;
        }
    }
    static int n,m;
    static int[] parent;
    static PriorityQueue<edge> pq = new PriorityQueue<edge>();
    static int result = 0;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        parent = new int[n+1];

        for(int i = 0; i<n+1;i++){
            parent[i] = i;
        }
        for(int i = 0; i<m;i++){
            st = new StringTokenizer(br.readLine());
            pq.add(new edge(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
        }

        for(int i = 0; i<m;i++){
            edge tmp = pq.poll();

            int a = find(tmp.s);
            int b = find(tmp.e);

            if(a==b) continue;
            union(a,b);
            result += tmp.v;
        }
        System.out.println(result);
    }
    public static int find(int a){
        if(a == parent[a]) return a;
        parent[a] = find(parent[a]);
        return parent[a];
    }
    public static void union(int a,int b){
        int aroot = find(a);
        int broot = find(b);

        if(aroot != broot){
            parent[aroot] = b;
        }
    }
}