<MST> BOJ 1197 최소 스패닝 트리

최소 스패닝 트리란?(최소 신장 트리)

최소 스패닝 트리란 그래프(트리 아닙니다)의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 의미합니다.

<그림 1>의 그래프에서 최소 스패닝 트리는 <그림 2>의 형태를 띄게 됩니다. 가중치가 10인 경로는 제외되었습니다. 예시에선 유일했지만 최소 스패닝 트리가 여러개일 수 있습니다.

<그림 1>	<그림 2>

최소 스패닝 트리 구하기 - kruskal 알고리즘

1. 모든 간선을 저정하고 가중치 순으로 정렬합니다. 혹시 정렬이 싫다면 priorityQueue를 사용해도 되지만 정렬하는게 맞다고 생각합니다.

//e개의 간선을 저장할 배열
Edge[] edges = new Edge[e];

//e개의 간선 정보를 for문을 통해 입력 받아 저장
for(int i = 0; i<e; i++){
  String[] temp = br.readLine().split(" ");
  int u = Integer.parseInt(temp[0]);
  int v = Integer.parseInt(temp[1]);
  int weigth = Integer.parseInt(temp[1]);
  
  edges[i] = new Edge(u, v, weight);
}

Arrays.sort(edges);

2. 모든 간선을 for문을 통해 돌면서 고를 수 있으면 고릅니다.
   고를 수 있으면 고른다는 것은 바로 사이클을 형성하지 않는 것을 의미합니다. 즉 이미 경로가 생성된 두 정점을 이으면 안된다는 의미입니다.(트리는 두 정점을 잇는 경로가 유일) 경로가 생성된 정점 여부를 판단하기 위해 Union-Find를 사용합니다.

int[] parent = new int[n];

for(int i = 0; i<n; i++){
  parent[i] = i;
}

for(int i = 0; i<e; i++){
  int u = edges[i].start;
  int v = edges[i].end;
  
  if(find(u) == find(v))
  	continue;
    
  union(u, v);
}

3. for문을 모두 돌고나면 최소 스패닝 트리가 형성됩니다.

과정을 따라가다보면 결국 최소 스패닝 트리를 구한 과정은 결국 트리 구성에 사용된 간선 중 최대 가중치의 최소값을 구하기 위한 과정과 동일하다는 것을 알 수 있습니다.

문제

간선의 정보를 입력받아 최소 스패닝 트리의 가중치의 합을 구하시오.

접근

최소 스패닝 트리를 구해주고 가중치의 값을 출력해주면 됩니다 :)

코드

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

class Edge implements Comparable<Edge> {
    int v1;
    int v2;
    int w;

    Edge(int v1, int v2, int w) {
        this.v1 = v1;
        this.v2 = v2;
        this.w = w;
    }

    public int compareTo(Edge that) {
        Integer u = this.w;
        Integer v = that.w;

        return u.compareTo(v);
    }
}

class baek__1197 {

    static int find(int n, int[] parent) {
        return parent[n] == n ? parent[n] : (parent[n] = find(parent[n], parent));
    }

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

        parent[r1] = r2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");

        int v = Integer.parseInt(temp[0]);
        int e = Integer.parseInt(temp[1]);

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

        for (int i = 0; i < e; i++) {
            temp = br.readLine().split(" ");

            int a = Integer.parseInt(temp[0]);
            int b = Integer.parseInt(temp[1]);
            int w = Integer.parseInt(temp[2]);

            edges[i] = new Edge(a, b, w);
        }

        Arrays.sort(edges);

        int answer = 0;

        for (Edge edge : edges) {
            int a = edge.v1;
            int b = edge.v2;

            int r1 = find(a, parent);
            int r2 = find(b, parent);

            if (r1 == r2)
                continue;

            answer += edge.w;
            union(r1, r2, parent);
        }

        System.out.print(answer);

    }
}