[Algorithm] Kruskal - 크루스칼

Kruskal Algorithm

---

Kruskal 알고리즘은 최소신장트리 MST(Minimum Spanning Tree)를 구하는 알고리즘이다. Greedy하게 N개의 정점을 N-1개의 간선을 이용해 최소 비용으로 연결한다. Kruskal 알고리즘의 기본 개념은 Greedy이기 때문에 간선 정보를 가중치 기준으로 오름차순 정렬한다. 다음으로, Union-Find 알고리즘을 이용해 모든 N개의 정점을 N-1개의 간선을 통해 최소 비용으로 연결할 수 있다. 따라서, Kruskal 알고리즘은 Greedy + Union-Find 알고리즘의 개념을 합쳐놓은 알고리즘으로 최소신장트리를 구하는데 이용된다.

[Data Structure] Minimum Spanning Tree - 최소 신장 트리

 

 

연습문제

---

프로그래머스

import java.util.*;

class Solution {

    private int[] parent;

    public void init(int n, int[][] costs) {
        //union-find algorithm 사용을 위한 자료구조 초기화
        parent = new int[n];
        for (int i = 0; i < parent.length; i++) parent[i] = i;

        //greedy algorithm 사용을 위한 간선 가중치 기준 정렬
        Arrays.sort(costs, (o1, o2) -> {
            return o1[2]-o2[2];
        });
    }

    public int solution(int n, int[][] costs) {
        init(n, costs);

        int answer = 0;
        for (int i = 0; i < costs.length; i++) {
            int px = find(costs[i][0]);
            int py = find(costs[i][1]);

            //이미 연결된 정점이라면
            if(px == py) continue;

            union(px, py);
            answer +=costs[i][2];
        }

        return answer;
    }

    public void union(int px, int py) {
        if(px <= py) parent[py] = px;
        else parent[px] = py;
    }

    public int find(int node) {
        if(parent[node] == node) return node;
        return find(parent[node]);
    }
}