알고리즘53 :: PROGRAMMERS_섬연결하기(Greedy) - (Collections sort, Greedy, MST, Kruskal)

크루스칼 알고리즘을 활용하여 문제를 해결할 수 있습니다. 

크루스칼 알고리즘은

간선의 가중치를 오름차순으로 정렬하고 

그 중 간선 리스트에서 사이클을 형성하지 않은 간선을 선택하여 가장 낮은 가중치를 먼저 선택하여 최소 스패닝 트리에 추가시켜 줍니다. (이 문제의 경우에는 ans 입니다.) 

 

 

 

 

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
class Solution {
    
    static int[] d;
    
    //연결 되어있는지 여부 확인 
    static int find(int nn){
        if(nn == d[nn]) return nn;
        else
            return d[nn] = find(d[nn]);
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        ArrayList<int[]> al = new ArrayList<>();
        for(int i=0; i<costs.length; i++)
            al.add(new int[]{costs[i][0], costs[i][1], costs[i][2]});
        
        //내림차순 정렬 
        Collections.sort(al, new Comparator<int[]>() {
 
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                return o1[2]-o2[2];
            }
        });
        d = new int[n];
        for(int i=0; i<d.length; i++){
            d[i] = i;
        }
        
        //최소 스패닝 트리 찾기 
        for(int i=0; i<costs.length; i++){
            int first = find(al.get(i)[0]);
            int second = find(al.get(i)[1]);
            int cost = al.get(i)[2];
            
            if(first!=second){
                d[first]=second;
                answer+=cost;
            }
        }
        
        return answer;
    }
}