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

[풀이]

해당 문제는 모든 섬들을 최소 비용으로 연결하는 문제이므로 크루스칼 알고리즘을 사용해 풀 수 있다.

크루스칼 알고리즘이란 모든 노드들을 최소 비용으롤 연결하는 알고리즘이다.

아래 링크에서 크루스칼 알고리즘에 대해 자세한 설명을 볼 수 있다.
https://tnwlswkd.tistory.com/42

[알고리즘] 크루스칼 알고리즘 ( Kruskal Algorithm)

 

 

최소 비용을 계산하기 위해 우선 두 섬을 연결하는 다리를 건설할 때 드는 비용을 기준으로 오름차순 정렬을 해주었다.

이 때 각 비용은 cost 배열의 2번째 배열에 존재하기 때문에 Arrays.sort 메서드와 Comparator를 사용했다.

 

연결을 하기 전엔 각자의 부모를 자기 자신으로 초기화한다.

 

그리고 최소 비용부터 cost를 순회하며 현재 섬의 부모가 같은 지 확인 후 

다를 경우 섬을 연결해준다.

[코드]

import java.util.Arrays;

class Solution {
    static int[] parent;
	
    public int solution(int n, int[][] costs) {
        int answer = 0;
    
    	Arrays.sort(array, (a, b) -> Integer.compare(a[1], b[1]));

        for(int idx=0;idx<n;idx++) { 
            parent[idx]=idx;
        }
        for(int[] cost : costs) {
            int from  = cost[0];
            int to = cost[1];
            int len = cost[2];

            if(Find(from) == Find(to)) continue;
            Union(from, to);
            answer+=len;
        }

        return answer;
    }
    
    public int Find(int idx) {
        if(parent[idx] == idx)  return idx;
        else {
            return Find(parent[idx]);
        }
    }

    public void Union(int idx1, int idx2) {
        int parent1 = Find(idx1);
        int parent2 = Find(idx2);

        parent[parent2] = parent1;
    }
}

[문제]

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

프로그래머스