백준 1197번 : 최소 스패닝 트리 java

이 문제는 최소 비용 신장 트리를 만드는 문제입니다.

최소 비용 신장 트리를 만들기 위한 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

크루스칼 알고리즘은 간단히 말해서 전체의 간선 중에서 가장 가중치가 낮은 간선들을 선택해서 최소 비용 신장 트리를 만드는 알고리즘입니다.

그리고 프림 알고리즘은 임의의 정점을 고른 후 그 정점에서 연결된 간선 중에서 가장 가중치가 낮은 간선을 선택하여 최소 비용 신장 트리를 만드는 알고리즘입니다.

저는 이 중에서 크루스칼 알고리즘을 이용하여 이 문제를 푸는 것을 선택하였습니다.

프림 알고리즘에 대한 설명은 아래의 링크에서 확인하실 수 있습니다.

프림 알고리즘 - 위키백과, 우리 모두의 백과사전

크루스칼 알고리즘에 대해서 예제 1번을 통해 설명드리겠습니다.

예제 1번은 다음과 같은 모양으로 이루어져 있습니다.

선택된 간선은 빨간색, 선택되지 않은 간선은 파란색으로 나타내겠습니다.

위와 같이 선택되지 않은 간선들이 있을 때 이 알고리즘은 최소 비용 신장 트리를 만들기 위해서 전체 간선 중에서 가장 가중치가 작은 간선을 선택합니다.

가중치가 작은 간선들을 선택하면서 만약 그 간선을 선택하였을 때 그래프가 생성된다면 그 간선은 선택하지 않고 그다음 간선을 선택합니다.

우선 크루스칼 알고리즘이 작동하는 모습을 보여드리겠습니다.

첫 번째로 가장 가중치가 낮은 간선을 선택하였습니다.

그다음으로 가중치가 낮은 간선이 선택되었습니다.

이미 1과 3은 2를 통해서 이어져 있기 때문에 1과 3을 이은다면 그래프가 되어 1과 3을 잇는 그래프는 선택하지 않습니다.

그럼 다음과 같은 최소 비용 신장 트리가 만들어집니다.

이를 코드를 보면서 조금 더 자세히 알아보도록 하겠습니다.

---

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

public class Main {
    static int[] parent;

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

        List<Node> l = new ArrayList<>();

        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 val = Integer.parseInt(st.nextToken());

            l.add(new Node(A, B, val));
        }

        Collections.sort(l);

        int sum = 0;
        parent = new int[V+1];
        for(int i = 1; i<=V; i++)
            parent[i] = i;

        //kruskal 알고리즘
        for(Node a : l){
            int A = a.A;
            int B = a.B;
            int val = a.val;

            if(find(A) == find(B))
                continue;

            sum += val;
            union(A, B);
        }

        System.out.println(sum);
    }

    static int find(int A){
        if(parent[A] == A)
            return A;
        else
            return find(parent[A]);

    }

    static void union(int A, int B){
        int a = find(A);
        int b = find(B);

        if(a != b)
            parent[b] = a;
    }
}
class Node implements Comparable<Node>{
    int A, B, val;

    Node(int A, int B, int val){
        this.A = A;
        this.B = B;
        this.val = val;
    }

    @Override
    public int compareTo(Node a){
        int val = a.val;

        if(this.val>val)
            return 1;
        else
            return -1;
    }
}

저는 다음과 같이 크루스칼 알고리즘을 구현하였습니다.

여기서 find와 union 함수를 집중해서 보시면 됩니다.

크루스칼 알고리즘을 통해서 최소 비용 신장 트리를 만들면 서로 연결되지 않은 부분이 생길 수 있습니다.

위의 그림과 같이 이어지지 않는 모습이 나온다면 이것을 우리는 최소 비용 신장 트리라고 부를 수 없습니다.

따라서 이러한 형태가 나온다면 위의 자료와 아래의 자료를 연결해주어야 합니다.

이를 위해서 find함수를 이용하여 새로 간선을 추가하였을 때 이게 원래 트리와 연결이 되어있는지를 확인하고 연결이
되어있지 않는다면 union함수를 이용하여 연결해주었습니다.