#프로그래머스_섬 연결하기 - Java 자바

#유형 : 크루스칼 알고리즘, 그리디

#난이도 : lv3

# 그리디 기반의 크루스칼 알고리즘으로 문제를 해결하였다. 크루스칼 알고리즘을 사용하기 위해서는 싸이클을 체크해야하고(트리에서는 싸이클을 허용하지 않는다.) 이를 위해 union-find 방식을 사용하였다.(간단하게 말하면 어느 집단에 속해있는지, 부모가 누구인지 체크하는것으로 싸이클을 체크하는 데 사용).

 

**크루스칼 알고리즘 순서

1. 입력받은 가중치들을 오름차순으로 정렬한다.

2. 정렬된 순서대로 Edge(u,v)가 다른 집합에 속해있다면, Edge(u,v,val)을 트리에 추가한다.

** 집합을 체크하기 위해 재귀 방식의 find를 사용하고, union을 통해 같은 집합으로 만든다.

 

 

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        ArrayList<Po> arrList = new ArrayList();
        int arr[] = new int[n+1];
        for(int i=1; i<=n; i++)
            arr[i] = i;
        
        for(int i=0; i<costs.length; i++){
            arrList.add(new Po(costs[i][0], costs[i][1], costs[i][2]));
        }
        Collections.sort(arrList);
        for(int i=0; i<arrList.size(); i++){
 
            Po p = arrList.get(i);
            int x = find(arr, p.u);
            int y = find(arr, p.v);
            if(x != y){
                union(arr, x, y);
                answer += p.val;
            }
        }
        return answer;
    }
    
    public static void union(int arr[], int u, int v){
        int x = find(arr, u);
        int y = find(arr, v);
        
        arr[x] = y;
    }
    
    public static int find(int arr[], int u){
        if(u == arr[u])
            return u;
        else
            return arr[u] = find(arr, arr[u]);
    }
    
    
    public class Po implements Comparable<Po>{
        int u;
        int v;
        int val;
        public Po(int u, int v, int val){
            this.u=u;
            this.v=v;
            this.val=val;
        }
        
        @Override
        public int compareTo(Po o){
            return this.val - o.val;
        }
    }
}