[알고리즘] 크루스칼(Kruskal) 알고리즘(feat. Java)

크루스칼 알고리즘

크루스칼 알고리즘은 그래프에서 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 최소 비용 신장 부분 트리란, 노드와 비용을 가지는 간선으로 이루어진 그래프에서 모든 노드를 방문하는 경로 중 최소 비용을 가지는 경로를 갖는 부분 트리를 뜻한다.

 

 

작동 방식

크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 또한, union find(서로소 집합) 알고리즘을 이용하기 때문에 사전에 공부를 해 두는 것이 이해에 도움이 된다.

 

• 주어진 그래프의 모든 간선을 간선의 연결비용을 오름차순 정렬
• 정렬된 간선 순서 대로 선택하면서, 간선의 양 끝 점을 Union한다. 이때에, 두 정점 모두 같은 집합에 있다면 포함X

 

이를 통해 최종적으로 선택된 간선을 연결한 것이 최소 비용 신장 트리이다. 

 

 

 

그림을 통한 알고리즘 흐름 이해

다음과 같은 그래프가 있을 때, 해당 그래프의 최소 비용 신장 트리를 구하는 단계를 알아보자

 

• 간선을 비용순으로 정렬(오름차순)
• 부모 리스트 초기화

 

• 정렬된 순서대로 단계 진행
• 2와 3을 union

 

• 그 다음 순서인 1과 6을 union 

 

• 노드 2와 4를 union -> 4과 (2, 3) 집합에 속하게됨

 

• 노드 1과 2를 union
• 노드 1의 집합(1,6)과 노드 2의 집합(2,3,4)과 노드 1의 집합에 속하게됨

 

• 노드 4와 5를 union -> 5가 노드 1의 집합에 속하게 됨
• 이로써 모든 노드를 방문

 

• 모든 노드가 한 집합에 속하게 되었으므로 이후의 모든 과정은 위 그림과 같이 추가 동작없이 넘어감

 

 

 

문제풀이를 통한 코드 이해

크루스칼 알고리즘을 이해하기 위해서는 위에서도 언급하였듯이 union find알고리즘에 대해서 알고 있어야 한다. 위의 링크를 걸어놓았으나 못보신 분들은 아래의 블로그를 참고하기 바란다.

 

https://codingralro.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%B0%94%EB%A1%9C-Union-Find-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

[알고리즘] 자바로 Union Find 구현하기

 

이를 통해 해결할 문제는 프로그래머스의 Lv3 섬 연결하기이다. 해당 문제에 대한 설명은 아래의 링크에 있다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

해당 문제의 풀이코드이다.

import java.util.*;
import java.util.stream.IntStream;

class Solution {
    public int[] parent;
    public class Bridge {
        int x;
        int y;
        int c;

        Bridge(int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }
    }
    public boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b) return false;

        if(a > b)
            parent[b] = a;
        else
            parent[a] = b;

        return true;
    }

    public int find(int x) {
        if(parent[x] == x) return x;
        return find(parent[x]);
    }
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        IntStream.range(0, n).forEach(i -> parent[i] = i);

        ArrayList<Bridge> blist = new ArrayList<>();
        IntStream.range(0, costs.length)
                .forEach(i -> blist.add(new Bridge(costs[i][0], costs[i][1], costs[i][2])));
        blist.sort(((o1, o2) -> o1.c - o2.c));

        for(Bridge b : blist) {
            if(union(b.x, b.y)) {
                answer += b.c;
            }
        }

        return answer;
    }
}

 

cost를 기준으로 오름차순하고 해당 배열을 돌면서 union을 했을 때 true가 나오면 비용을 더하였다.