Kruskal 알고리즘이란

탐욕법(greedy method)의 일종으로 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것. MST(최소 비용 신장 트리)를 구할 때 사용된다.

동작 방식

1. 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선들을 차례대로 연결하면서 Cycle을 이루지 않는 간선만 해의 집합에 추가한다. (Cycle 여부는 union-find로 판단)

관련 문제 풀이

• 프로그래머스의 탐욕법 문제 중 '섬 연결하기' 문제풀이

import java.util.*;

class Solution {
    /* 
    사이클 확인을 위해 union-find 및
    node의 root를 저장하는 배열 선언
    */
    int[] root = new int[100];
    
    // Root node 찾는 함수
    public int find(int x) {
        if (root[x] == x) {
            return x;
        } else {
            return find(root[x]);
        }
    }
    
    // x 노드에 y를 연결하는 함수, Cycle이 없으면 y의 Root는 x의 Root가 된다.
    public boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        
        // Root가 같을 시 사이클이 존재한다
        if (x == y) return false;
        
        root[y] = x;
        
        // 사이클 없음
        return true;
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        // 적은 비용 순으로 오름차순 정렬
        Arrays.sort(costs, new Comparator<int[]>() {
           public int compare(int[] o1, int[] o2) {
               return o1[2] - o2[2];
           } 
        });
        
        // 루트가 자기자신을 가리키도록 초기화
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        
        // Kruskal 알고리즘
        for (int i = 0; i < costs.length; i++) {
            if (union(costs[i][0], costs[i][1])) {
                answer += costs[i][2];
            } 
        }
        
        return answer;
    }
}

참고사이트
https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html