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

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

1197번: 최소 스패닝 트리

 

문제

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

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

입력

첫째 줄에 정점의 개수 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 

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1 

3

---

그냥 Minimum spanning tree(MST) 를 구하면 된다.

 

주어진 데이터를 edge list 형태로 저장하는데, 중요한 것은

 

가중치를 기준으로 오름차순으로 저장한다.

 

이를 위해서 우선순위큐 형태의 자료구조를 채택한다.

 

우선순위큐에 엣지 정보가 저장되면,

 

현재 상태에서 가장 가중치가 최소인 엣지를 선택하고,

 

사이클이 이루어지지 않도록 노드를 연결한다.

 

이를 위해서 유니온&파인트 알고리즘을 이용하여

 

사이클을 이루는지 여부를 파악해야 한다.

 

구현은 어렵지 않다.

 

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static PriorityQueue<Edge> pq;
    static int [] parent;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(stk.nextToken()); // 노드 개수
        int e = Integer.parseInt(stk.nextToken()); // 에지 개수
        pq = new PriorityQueue<>();
        for (int i = 0; i < e; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int cost = Integer.parseInt(stk.nextToken());
            pq.add(new Edge(a, b, cost));
        }

        parent = new int[v + 1];
        for (int i = 1; i <= v; i++)
            parent[i] = i; // 유니온&파인트 배열 초기화
        int used = 0;
        int min_cost=0;
        while(used < v-1){
            Edge now_edge = pq.poll();
            if(find(now_edge.s) != find(now_edge.e)){
                // 부모가 다르면 사이클이 형성되지 않는 것
                union(now_edge.s, now_edge.e); // 그러면 연결
                min_cost+=now_edge.w;
                used++;
            }
        }
        System.out.println(min_cost);
    }
    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b)
            parent[b] = a;
    }
    static int find(int a){
        if(parent[a] == a)
            return a;
        else return parent[a] = find(parent[a]);
    }
    static class Edge implements Comparable<Edge> {
        int s;
        int e;
        int w;

        public Edge(int s, int e, int w) {
            this.s = s;
            this.e = e;
            this.w = w;
        }

        @Override
        public int compareTo(Edge v) {
            return this.w > v.w ? 1 : -1;
        }
    }
}