[240329] 알고리즘 리부트 41일차 - 프로그래머스 섬 연결하기 자바

최소 비용을 구하는 문제이다. 먼저 각 섬의 루트노드를 저장할 배열을 선언한다. 이 때 초기 값은 각자의 인덱스 값이다. 즉, 각자가 루트노드인 것이고 각자의 집합에 속해있는 것이다. 그 다음 건설 비용이 적은 순서대로 먼저 정렬해준 후 순서대로 연결을 해본다. 이 때 연결하기 전 두 섬의 연결되어 있는지는 루트 노드를 찾아서 비교한다. 만약 다르다면 다리 연결에 드는 비용을 정답 변수에 더해주고 유니언 메소드를 통해 한쪽 루트노드를 다른 한 쪽으로 변경해서 합쳐준다. 같을 때 다리를 놓는다면 사이클이 생겨 비효율적이고 최소 비용이 될 수 없다. 이 작업을 반복하며 다리의 갯수가 n-1개 일 때 작업을 완료하면 된다. n개를 연결하는 최소 갯수는 n-1개 이기 때문이다.

import java.util.*;

class Solution {
    public static int[] parents;
    public static int find(int i){
        if(parents[i] == i) return parents[i];
        
        parents[i] = find(parents[i]);
        return parents[i];
    }
    
    public static void union(int i, int j){
        int rootI = find(i);
        int rootJ = find(j);
        parents[rootJ] = rootI;
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int connected = 1;
        
        parents = new int[n];
        
        for(int i = 0; i < n; i++){
            parents[i] = i;
        }
        
        Arrays.sort(costs, (o1, o2)->          
            Integer.compare(o1[2], o2[2]));
        
        for(int[] edge : costs){            
            
            if(connected == n-1) break;
            
            if(find(edge[0])!=find(edge[1])) {
                union(edge[0], edge[1]);
                answer+=edge[2];
            }
                      
        } 
        
        return answer;
    }
}