프로그래머스(섬 연결하기)

문제

코드

성공 코드

import java.util.*;

class Solution {
    private int rootNodeStore[];
    private int getRootNode(int idx){
        if(rootNodeStore[idx] == idx) return idx;
        else {
            rootNodeStore[idx] = getRootNode(rootNodeStore[idx]);
            return rootNodeStore[idx];
        }
    }

    private void renewRootNode(int a, int b){
        a = getRootNode(a);
        b = getRootNode(b);
        if(a > b)
            rootNodeStore[a] = b;
        else
            rootNodeStore[b] = a;
    }

    private boolean isSameRootNode(int a, int b){
        return getRootNode(a) == getRootNode(b);
        //같은 부모를 갖고 있다면 사이클 발생
    }
    
    public int solution(int n, int[][] costs) {
        int length = Math.max(n, costs.length);
        rootNodeStore = new int[length];
        for(int i = 0; i < length; i++)
            rootNodeStore[i] = i;

        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        int sum = 0;
        for(int i = 0; i < costs.length; i++){
            int[] ing = costs[i];
            if(!isSameRootNode(ing[0], ing[1])){
                renewRootNode(ing[0], ing[1]);
                sum += ing[2];
            }
        }
        return sum;
    }
}