[백준 1197 | MST] 최소 스패닝 트리

 

풀이

최소 스패닝 트리를 구하는 데에는 크게 2가지 알고리즘 (크루스칼 알고리즘, 프림 알고리즘)이 알려져 있습니다. 위 문제는 최소 스패닝 트리의 가중치 값을 묻는 기본적인 문제이기 때문에, 개인적으로 구현하기 편했던 크루스칼 알고리즘을 사용하였습니다. 

 

크루스칼 알고리즘을 사용하기 위해서는 먼저 상호 배타적 집합 (Disjoint Set)을 먼저 구현해야 합니다. 크루스칼 알고리즘은 프림 알고리즘 과는 다르게, 간선을 가중치 순으로 먼저 정렬한 후에, 가중치가 작은 간선부터 이어 나가면서, 해당하는 간선의 두 정점이 이미 같은 트리에 속해 있는지를 판단해야 합니다. 예를 들어, 1과 2를 잇는 가중치 1인 간선을 추가하려고 할 때, 1과 2를 이어주는 경로가 이미 존재한다면 해당 간선을 추가해서는 안된다는 것입니다. 

 

따라서 간선을 그 가중치 순으로 정렬한 뒤에, 간선이 가리키는 두 정점을 잇는 경로가 트리에 이미 존재하는지를 확인하고, 없는 경우에만 해당 간선을 추가하여 트리를 만들어주면 됩니다. 이때, 간선이 하나 추가될 때마다, 해당 간선의 가중치 값을 더해주면 됩니다. 

 

 

소스 코드 (JAVA)

import java.util.*;
import java.io.*;

public class Kruskal {
    public static int[] parent;
    public static ArrayList<Edge> edgeList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token = new StringTokenizer(br.readLine());

        int v = Integer.parseInt(token.nextToken());
        int e = Integer.parseInt(token.nextToken());
        parent = new int[v];
        edgeList = new ArrayList<Edge>();

        for(int i=0;i<v;i++) parent[i] = i;
        for(int i=0;i<e;i++){
            token = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(token.nextToken()) - 1;
            int end = Integer.parseInt(token.nextToken()) - 1;
            int val = Integer.parseInt(token.nextToken());
            edgeList.add(new Edge(start, end, val));
        }
        Collections.sort(edgeList);

        long sum = 0;
        for(int i=0; i<edgeList.size(); i++){
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.v1, edge.v2)) {
                sum += edge.cost;
                union(edge.v1, edge.v2);
            }
        }

        bw.write(sum+"\n");
        bw.flush();
        bw.close();
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y) parent[y] = x;
    }

    public static int find(int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    public static boolean isSameParent(int x, int y) {
        return find(x) == find(y);
    }
}

class Edge implements Comparable<Edge> {
    int v1, v2, cost;
    Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        if (this.cost < o.cost) return -1;
        else if(this.cost == o.cost) return 0;
        else return 1;
    }
}