크루스칼 알고리즘

 

 

 

 

크루스칼(Kruskal) 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘 중 하나입니다. 최소 신장 트리는 가중치가 있는 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소인 트리를 말합니다.

크루스칼 알고리즘의 동작은 다음과 같습니다:

1. 그래프의 모든 간선을 가중치 순으로 오름차순으로 정렬합니다.
2. 빈 신장 트리를 생성합니다.
3. 가장 작은 가중치를 가진 간선부터 시작하여, 해당 간선의 양 끝점이 서로 다른 집합에 속해 있다면, 간선을 신장 트리에 추가합니다. 이를 위해 Union-Find 자료구조를 사용하여 각 정점이 어떤 집합에 속해 있는지 확인합니다.
4. 모든 간선을 처리할 때까지 3단계를 반복합니다.

크루스칼 알고리즘은 간선의 가중치를 기준으로 처리하기 때문에 그리디 알고리즘으로 분류됩니다. 이 알고리즘은 그래프가 연결되어 있을 때(모든 정점이 하나의 연결 요소에 속할 때)만 사용할 수 있습니다. 또한, Union-Find 자료구조를 사용하여 간선의 연결 여부를 확인하기 때문에, Union-Find 자료구조의 성능에 따라 알고리즘의 성능이 영향을 받습니다.

크루스칼 알고리즘의 시간 복잡도는 주로 간선 정렬에 의해 결정됩니다. 간선을 정렬하는 데 O(E log E)의 시간이 소요되고, Union-Find 자료구조를 사용하여 간선의 연결 여부를 확인하는 데는 O(log V)의 시간이 걸립니다. 따라서, 최종적으로 크루스칼 알고리즘의 시간 복잡도는 O(E log E)입니다. 여기서 E는 간선의 개수, V는 정점의 개수입니다.

 

 

 

 

---

프로그래머스 - 섬 연결하기

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parent = new int[n];
        
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        };
    
        Arrays.sort(costs, (o1, o2) -> o1[2]-o2[2]);
        for (int i = 0; i < costs.length; i++) {
            if(findParent(parent, costs[i][0]) != findParent(parent, costs[i][1])) {
                answer += costs[i][2];
                union(parent, costs[i][0], costs[i][1]);
            }
        }    
        
        return answer;
    }
    
    public void union(int[] parent, int cur, int next) {
        int p1 = findParent(parent, cur);
        int p2 = findParent(parent, next);
        if (p1 < p2)
            parent[p2] = p1;
        else
            parent[p1] = p2;              
    }
    
    public int findParent(int[] parent, int node) {
        if (parent[node] == node)
            return node;
        return findParent(parent, parent[node]);
    }
}