[Java] BaekJoon 1197. 최소 스패닝 트리 (java) (Kruskal) (union-find)

문제출처: https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

문제이해

 

목표

가중치 합이 최소인, 최소 스패닝 트리를 구하시오. 

결과는 가중치 합을 출력

 

풀이

Kruskal의 방법으로 풀었다. 

1. PriorityQueue(오름차순으로 정렬) 안에 모든 간선을 담는다.

2. 제일 낮은 간선을 뽑는다.

   -> 간선으로 연결되어 있는 두 노드가 같은 그래프안에 있으면 루프가 생김으로 이 간선은 버린다.

   -> 루프가 생기지 않으면 

        - 만약 두 노드 모두 어느 곳에서 포함되어 있지 않으면 이 두 노드의 부모를 일치시켜 그래프 그룹을 이룬다

        - 만얀 두 노드가 포함된 그래프가 다르면(부모노드가 다르면) union-find를 이용하여 부모노드를 일치시킴

       그리고 (해당 간선의 비용을 가중치에 추가)

3. 문제의 제약조건에서는 마이너스인 간선도 있을 수 있다고 했기 때문에 모든 간선을 조사하는게 좋다. 

---

소스코드

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

// https://www.acmicpc.net/problem/1197
public class 최소스패닝트리 {

    private static int V;
    private static int E;
    private static long answer;
    private static int[] vertexes;

    static class Edge implements Comparable<Edge> {
        int vtx1;
        int vtx2;
        int price;
        public Edge(int vtx1, int vtx2, int price) {
            this.vtx1 = vtx1;
            this.vtx2 = vtx2;
            this.price = price;
        }

        @Override
        public int compareTo(Edge o) {
            return this.price - o.price;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        V = Integer.parseInt(strArr[0]);
        E = Integer.parseInt(strArr[1]);
        answer = 0;
        PriorityQueue<Edge> pq = new PriorityQueue();
        for (int i = 0; i < E; i++) {
            strArr = br.readLine().split(" ");
            pq.add(new Edge(Integer.parseInt(strArr[0]), Integer.parseInt(strArr[1]), Integer.parseInt(strArr[2])));
        }

        // union-find를 위한 배열
        vertexes = new int[V+1];
        for (int i = 1; i <= V; i++) {
            vertexes[i] = i;
        }
        Edge edge = pq.poll();
        vertexes[edge.vtx2] = edge.vtx1;
        answer += edge.price;

        // 크루스칼
        while(!pq.isEmpty()){
            edge = pq.poll();
            int vtx1Parent = find(edge.vtx1);
            int vtx2Parent = find(edge.vtx2);
            // Union
            if(vtx1Parent == vtx2Parent){
                continue;
            } else if(vtx1Parent < vtx2Parent){
                vertexes[vtx2Parent] = vtx1Parent;
            } else {
                vertexes[vtx1Parent] = vtx2Parent;
            }
            answer += edge.price;
        }

        System.out.println(answer);
    }

    private static int find(int vtx){
        if(vertexes[vtx] == vtx){
            return vtx;
        }
        return vertexes[vtx] = find(vertexes[vtx]);
    }
}

 

---

정리

• Minimum Spanning Tree (최소 신장 트리, 최소 스패닝 트리)의 성질에 대해 다시 한 번더 기억
• MST 알고리즘 중 kruskal과 prim이 있고 이들의 개념을 다시 한번 더 기억하자
• Union-find 알고리즘 그래프 그룹을 구분하고 일치시키는데 가장 편한 알고리즘
• Comparable을 implements하여 PQ에 적용 가능
  -> Comparator는 class이기 때문에 람다함수로 Comparator 파라미터 자리에 compare와 함께 구현할 수 있음