[프로그래머스-JAVA] Lv.3 섬 연결하기

알고리즘 : 최소비용신장트리 

최소비용신장트리를 완성해가는 데 union find 알고리즘을 사용해서 사이클을 피하는 방식이다.

Find에서 경로압축을 진행한다.

 

처음에 루트를 찾아가는 find함수에서 루트노드까지 재귀로 찾아가고

나중에 return 되면 자식 노드들의 부모가 전부 루트노드로 갱신되며 추후의 탐색비용이 줄어드는 경로압축이 진행된다.

 

find함수로 루트 노드를 찾아 다를 경우 union한다.

이 과정에서 간선 사이 비용을 오름차순으로 정렬하여, 최솟값을 선택하면서 계속한다.

최종적으로 간선의 수가 n-1 개일 경우 트리가 완성되었으므로 break한다.

 

---

문제설명

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

프로그래머스

---

내 코드

 

import java.util.*;

class Solution {
    private static int[] parent;
    // 경로 압축 - find
    private static int find(int x){
        if (parent[x] == x){
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    // union
    private static void union(int a,int b){
        int aRoot = find(a);
        int bRoot = find(b);
        
        if (aRoot != bRoot){
            parent[aRoot] = bRoot;
        }
    }
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int edges = 0;
        // parent 초기화
        parent = new int[n];
        for (int i = 0; i < n; i++){
            parent[i] = i;
        }
        // 오름차순 정렬
        Arrays.sort(costs, (a,b) -> Integer.compare(a[2],b[2]));
        // 최소 비용을 선택하는 데 둘의 루트가 다르면 union
        for (int[] edge : costs){
            if (edges == n-1) break;
            
            int aRoot = find(edge[0]);
            int bRoot = find(edge[1]);
            
            if (aRoot != bRoot){
                union(aRoot,bRoot);
                edges++;
                answer += edge[2];
            }
        }
        return answer;
    }
}