[알고리즘] 최소신장트리 - Kruskal 알고리즘

600g (Kim Dong Geun)·2020년 4월 10일

프로그래머스에서 섬 문제를 풀다가, 아 이거 최소신장트리로 풀면되는 문제인데 왜 레벨3일까?라고 생각하고
구현 못하고 있는 내 자신을 보고는 이 글을 쓰겠다고 다짐을 했다.

최소 신장 트리란?

Minimum Spanning Tree를 한글로 번역하면 최소 신장트리로
각 간선의 가중치가 주어질때 모든 섬을 연결하는 최소 비용을 구하는 것 이다.
즉 모든 경우의 신장트리에서 최소비용의 신장 트리를 선택하는 것이 MST의 핵심이다.

MST의 특징

n개의 정점을 가지는 그래프는 반드시 n-1개만의 간선을 선택해야한다. (신장트리 조건)
간선의 합이 최소여야한다.
사이클을 포함하지 않아야 한다.

MST의 사용 사례

도로 건설
도시들을 모두 연결 하면서 도로의 길이가 최소가 되도록 하는 문제.
전기 회로
단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제.
섬문제 (프로그래머스)
최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용 구하는 문제.

MST의 구현방법

Kruskal 알고리즘
Kruskal 알고리즘은 탐욕적인 방법을 이용해서 모든 정점을 연결하는 간선의 합을 최소 비용으로 연결하는 해답을 구하는 것.
Greedy한 방식을 사용하는 대표적인 알고리즘
Prim의 MST 알고리즘
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

Kruskal 알고리즘 구현

크루스칼 알고리즘은 앞서 Greedy 알고리즘을 사용한다고 하였다.
Greedy알고리즘을 사용하면서 지켜야 할 조건이 한 개있다.

사이클을 형성해서는 안 된다.

닥치는 대로 Greedy하게 간선을 포함시킨다면 당연히 사이클이 형성될 수 밖에 없다.
그래서 간선이 포함됐는지 안 포함됐는지 확인하는 방법이 바로 Union-Find이다.

Union- Find 소스는 다음과 같다.

    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) {
        x = find(x);
        y = find(y);
        if(x == y) return true;
        else return false;
    }

간단하게 해석하자면, union을 통해서 네트워크를 형성하고, find를 통해서 네트워크가 같은지 비교한다고 보면된다.

두개의 간선의 parent를 비교한다. 두가지의 경우의 수가 생긴다.

두 간선의 Parent가 같을 때)
같은 네트워크를 형성함 있으므로, 둘을 연결할 시 사이클을 형성한다.
따라서 비교하는 하나의 간선은 Path가 될 수 없다.
두 간선의 Parent가 다를 때,
같은 네트워크안에 속해있지 않으므로, 비교하는 하나의 간선은 Path가 될 수 있다.
따라서 Path에 포함하고 같은 parent를 향하도록 하여 두 간선은 동일한 네트워크임을 표시한다.

따라서 위 union find 코드를 이용하여 작성한 코드는 다음과 같다.

import java.util.ArrayList;
import java.util.Collections;

class Edge implements Comparable<Edge> {
    int v1;
    int v2;
    int 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;
    }
}
public class Main {
    public static int[] parent;
    public static ArrayList<Edge> edgeList;
	
    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) {
        x = find(x);
        y = find(y);
        if(x == y) return true;
        else return false;
    }
    public static void main(String[] args) {
        edgeList = new ArrayList<Edge>();
        edgeList.add(new Edge(1,4,4));
        edgeList.add(new Edge(1,2,6));
        edgeList.add(new Edge(2,3,5));
        edgeList.add(new Edge(2,4,3));
        edgeList.add(new Edge(2,5,7));
        edgeList.add(new Edge(2,6,8));
        edgeList.add(new Edge(3,6,8));
        edgeList.add(new Edge(4,5,9));
        edgeList.add(new Edge(5,6,11));
		
        parent = new int[7];
        for(int i = 1; i <= 6; i++) {
            parent[i] = i;
        }
		
        Collections.sort(edgeList);
		
        int 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);
            }
        }
		
        System.out.println(sum);
    }	
}