[백준/Java] 1197 : 최소 스패닝 트리

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

 

이 번에 풀어본 문제의 종류는 MST(최소 신장 트리)입니다. 최소 신장은 주어진 그래프의 부분 그래프 중 모든 정점을 포함하는 트리를 말합니다. 여기서 MST란 이를 최소한의 비용(기존 간선)으로 이루어진 그래프입니다.

 

MST 알고리즘을 풀이는 2가지 대표 알고리즘이 있습니다. 크루스칼 알고리즘과 프림 알고리즘이 존재하는데 크루스칼을 활용해 문제를 풀이해보겠습니다.

 

크루스칼 알고리즘은 유니온 파인드라는 알고리즘을 사용합니다. 유니온 파인드는 서로의 집합을 확인하는 알고리즘입니다. parent[] 배열을 통해 최상위를 확인하여 서로 같은 집단인지 확인하며 문제를 풀이하면 됩니다.

 

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

public class Backjoon_1197_최소_스패닝_트리 {
    public static class Node{
        int v1;
        int v2;
        int value;

        public Node(int v1, int v2, int value) {
            this.v1 = v1;
            this.v2 = v2;
            this.value = value;
        }
    }

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

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        parent = new int[V+1];
        PriorityQueue<Node> pq = new PriorityQueue<>((p1, p2) -> p1.value - p2.value);


        for(int i = 1 ; i <= V ; i++){
            parent[i] = -1;
        }

        for(int i = 0 ; i < E ; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            pq.offer(new Node(v1,v2,value));
        }

        int count = 0;
        int answer = 0;

        while(true){

            if(count == V - 1){
                break;
            }

            Node node = pq.poll();

            if(isSame(node.v1, node.v2)) continue;

            union(node.v1, node.v2);
            count++;
            answer += node.value;


        }
        System.out.println(answer);

    }

    public static int find(int value){
        if(parent[value] < 0){
            return value;
        }

        return parent[value] = find(parent[value]);
    }

    public static void union(int a, int b){
        a = find(a);
        b= find(b);


        if(a < b){
            parent[a] += parent[b];
            parent[b] = a;
        }else{
            parent[b] += parent[a];
            parent[a] = b;
        }
    }

    public static boolean isSame(int a, int b){
        return find(a) == find(b);
    }
}