[プログラマー]コードテスト練習-貪欲レベル3島をつなぐ



Solution.java

import java.util.*;

class Solution {
    int[] p;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        p = new int[n];
        
        for (int i = 0; i < n; i++) p[i] = i;
        
        Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));
        
        for (int[] cost : costs) {
            int a = find(cost[0]);
            int b = find(cost[1]);
            
            if (a != b) {
                union(a, b);
                answer += cost[2];
            }
        }
        
        return answer;
    }
    
    int find(int child) {
        if (p[child] == child) return child;
        
        return p[child] = find(p[child]);
    }
    
    void union(int a, int b) {
        p[b] = a;
    }
}
最小身長木問題.union-findアルゴリズムを実現し解決した.
出典:プログラマーコードテスト練習、https://programmers.co.kr/learn/challenges