1197 최소 스패닝 트리(Java)

최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

풀이

최소비용신장트리를 구하는 문제이다.
최소비용신장트리를 구하는 알고리즘은 다음과 같다.

1. 모든 간선을 비용순으로 정렬한다.
2. 비용이 가장 작은 간선을 구한다.
3. 해당 간선을 취했을 때 사이클(트리가 아닌 그래프가 되는것)이 발생하지 않는지를 확인한다.
4. 사이클이 생기지 않는다면 해당 간선을 취하고 만약 생긴다면 간선을 취하지 않는다.

필자는 1,2번을 우선순위큐를 이용하여 구현하였고 3,4번을 union-find를 이용하여 구현하였다.

코드

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

public class Main{

    static class Node implements Comparable<Node>{
        int start;
        int end;
        int dist;

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

        @Override
        public int compareTo(Node o){
            return dist - o.dist;
        }
    }

    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());



        int[] parent = new int[v+1];
        for (int i = 1; i < v + 1; i++) {
            parent[i] = i;
        }

        Queue<Node> queue = new PriorityQueue<>();

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            queue.add(new Node(a, b, c));
        }

        int ans = 0;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int start = node.start;
            int end = node.end;
            int dist = node.dist;

            if (find(parent, start) != find(parent, end)) {
                union(parent, start, end);
                ans += dist;
            }
        }

        System.out.println(ans);

    }

    static int find(int[] parent, int n) {
        if (parent[n] != n) {
            parent[n] = find(parent, parent[n]);
        }
        return parent[n];
    }

    static void union(int[] parent, int a, int b) {
        a = find(parent, a);
        b = find(parent, b);

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