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

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

[문제 풀이]

크루스칼 알고리즘을 이용하여 문제를 풀었습니다.

 

섬 연결하기 문제는 전형적인 최소신장트리 문제입니다. 최소신장트리의 종류는 몇 가지가 존재하는데 그 중 하나가 크루스칼 알고리즘입니다. 알고리즘에 대한 내용은 아래 링크를 참고 바랍니다.

 

https://steady-life.tistory.com/128

서로소 집합(Disjoint Set, Union-Find)

https://steady-life.tistory.com/124

 

[JAVA]

import java.util.Arrays;
import java.util.Comparator;

class Solution {
	static int[] island;
    
    public static int unionFind(int i){
        if(island[i] == i)
            return i;
        else
            return unionFind(island[i]);
    }
	
	public static int solution(int n, int[][] costs) {
		
        int answer = 0;
        island = new int[n];
        
        Arrays.sort(costs, new Comparator<int[]>(){
           public int compare(int[] o1, int[] o2){
               return o1[2] - o2[2];
           } 
        });
        
        for(int i = 0; i < n; i ++)
            island[i] = i;
        
        for(int[] item : costs){
            int a = unionFind(item[0]);
            int b = unionFind(item[1]);
            
            if(a != b){
                answer += item[2];
                island[a] = b;
            }
        
        }
        
        
		return answer;
	}
}