알고리즘82 :: 프로그래머스_섬연결하기(MST, 크루스칼)

import java.util.ArrayList;
import java.util.Collections;
class Solution {
    static class MST implements Comparable<MST>{
        int start;
        int end; 
        int value;
        MST(int start, int end, int value){
            this.start = start;
            this.end = end;
            this.value = value;
        }
        @Override
        public int compareTo(MST o) {
            // TODO Auto-generated method stub
            return this.value - o.value;
        }
    }
    static int[] parents;
    static ArrayList<MST> al = new ArrayList<>();
    static int find(int n) {
        if(parents[n] == n )
            return n;
        else
            return parents[n] = find(parents[n]);
    }
    
    static void merge(int u, int v) {
        int f_u = find(u);
        int f_v = find(v);
        if(f_u != f_v) {
            parents[f_v] = f_u;
        }
    }
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        parents = new int[n+1];
        for(int i=1; i<=n; i++) {
            parents[i] = i;
        }//초기값을  주고
        
        for(int i=0; i<costs.length; i++) {
            al.add(new MST(costs[i][0],costs[i][1],costs[i][2]));
        }//start, end, value 넘겨주고 
        
        int ans = 0;
        Collections.sort(al);
        for(int i=0; i<al.size(); i++) {
            int u = al.get(i).start;
            int v = al.get(i).end;
            int value = al.get(i).value;
            if(find(u)!=find(v)) {
                merge(u,v);
                ans += value;
            }
        }//end of for 
        
        return ans;
    }
}

예전에 포스팅 할때는 사이클이 형성되는지 체크를 안했는데... 굉장히 오류가 아닌가 싶다. 

 

MST 는 최소 스패닝 트리를 구성하고 그중에서 가중치의 합이 제일 작은것을 찾는 과정이다. 

 

따라서, 단순 MST 구현, 크루스칼, 프림 알고리즘 활용하면 해결할 수 있는데 비교적 크루스칼이 쉽다.