[백준] 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

문제해결방법

MST를 구하는 방법은 두 가지가 있다.(Kruskal 알고리즘 / Prim 알고리즘)

Kruskal 알고리즘 : 간선의 양 끝 점이 사이클을 형성하지 않는 최소 간선만을 선택하는 방법

Prim 알고리즘 : 한 정점에서 시작해서 인접한 정점으로 갈 수 있는 최소 간선을 선택하는 방법

POINT

Kruskal 알고리즘으로 문제를 푸는 경우, Union-Find 자료구조를 이용해 간선의 양 끝 점이 사이클을 형성하는지 확인한다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
class comp implements Comparator<long[]> {
    @Override
    public int compare(long[] arg0, long[] arg1) {
        return Long.compare(arg0[2], arg1[2]);
    }
}
 
public class Main1197_최소스패닝트리 {
    
    public static int V, E;
    public static int[] parent;
    public static long[][] edge;
 
    public static void makeSet() {
        for(int i=1; i<=V; i++) parent[i] = i;
    }
    
    public static int find(int a){
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
    
    public static void union(int a, int b) {
        int ap = find(a);
        int bp = find(b);
        parent[bp] = ap;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        parent = new int[V+1];
        makeSet();
        edge = new long[E][3];
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            edge[i][0] = Integer.parseInt(st.nextToken());
            edge[i][1] = Integer.parseInt(st.nextToken());
            edge[i][2] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(edge, new comp());
        long sum = 0;
        for(int i=0; i<E; i++) {
            if(find((int)edge[i][0])!=find((int)edge[i][1])) {
                sum += edge[i][2];
                union((int)edge[i][0], (int)edge[i][1]);
            }
        }
        System.out.println(sum);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.