プログラマー-島を接続[java]

質問元:https://programmers.co.kr/learn/courses/30/lessons/42861

問題の説明

n個の島の間に橋を建設する費用(費用)については、すべての島が最小の費用で互いに通行できるようにする解決策を完了し、必要な最小の費用を返してください.
橋を何度も渡っても、たどり着けば通行できます.例えば、A島とB島の間に橋があり、B島とC島の間に橋があれば、A島とC島は互いに通行することができる.
せいげんじょうけん

島の個数nは1以上100以下である.

コストの長さは(n−1)*n)/2以下である.

任意iの場合、cost[i][0]とcost[i][1]は橋を結ぶ2つの島の番号を含み、cost[i][2]はこの2つの島を結ぶ橋を建設するのに必要な費用である.

同じ接続は2回付与されません.また、順序が変更されると、同じ接続とみなされます.つまり、0と1の間に接続が確立されている場合、1と0は必要ありません.

すべての島の間の橋梁建設費用をあげない.この場合,二つの島の間に建設することは不可能であると考えられる.
つながっていない島はありません.

入力例
n = 4, costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
サンプル出力
4
I/O例説明
コストは下図のように、緑のパス接続を使用すると、すべての人が通過できるように最小限のコストで使用できます.

問題を解く

import java.util.*;

class Solution {
    
    static int[] parents;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);
        
        
        parents = new int[n];
        
        for(int i = 0; i < parents.length; i++)
            parents[i] = i;
        
        for(int[] set : costs) {
            int from = set[0];
            int to = set[1];
            int weight = set[2];
            
            if(unionFind(from) == unionFind(to)) continue;
            
            answer += weight;
        	parents[unionFind(to)] = unionFind(from);
            

        }
        return answer;
    }
    
    public static int unionFind(int node) {
        if(parents[node] == node)
            return parents[node];
        return unionFind(parents[node]);
    }
}

MST(minimum spanning tree)を求めます.MSTを得るためには,Kruscal'sアルゴリズムを理解し,その中のunionFindグラフアルゴリズムを理解する必要がある.
MST−最小伸長木とは、最小接続周期を含まない生成木に接続された幹線上にすべての頂点が重み付け値を有する場合、重み付け費用が最小となる木を意味する.ここで、頂点の最小接続周期をすべて含まない生成木の幹線の数は、頂点がnで表される場合、常にn−1である.
参考資料:https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
Union-Find-複数のノードが存在する場合、2つのノードを選択することにより、現在の2つのノードが同じパターンに属するか否かを判別するアルゴリズム.
参考資料:https://m.blog.naver.com/ndb796/221230967614
kruscal'sアルゴリズム-すべてのノードを最小コストで接続するアルゴリズムは、最小拡張ツリー(MST)を作成する代表的なアルゴリズムです.
参考資料:https://m.blog.naver.com/ndb796/221230994142
解答方法

(出発点、到着点、料金)からなる3つを料金基準で昇順に並べます.
(最低コストの幹線から貼るため)

整数長の配列を作成し、インデックスで初期化します.
(全員がルートノードに設定)

コストマトリクスを迂回して接続し、UnionFindアルゴリズムを使用してMSTを作成します.
ex)[1,2,1]では->ノード1がノード2に接続されているため,ノード1とノード2のルートが決定して異なる場合,ノード2のルートがノード1のルートに更新される.ルートが同じ場合は同じグラフィックに属するため、接続時にループするのでスキップします.