[프로그래머스/Java] 42861 섬 연결하기

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

🔍  해결 과정

크루스칼 알고리즘을 활용하여 문제를 해결하였습니다. 크루스칼 알고리즘에 대한 설명 내용은 다음 링크에 있습니다.

https://devjuice.tistory.com/41

[핵심정리] 크루스칼 알고리즘

 

이를 활용함으로써 시간복잡도를 O(ElogE) (E: costs 배열의 길이)로 설계할 수 있습니다.

 

---

✏️ 코드

import java.util.*;

class Solution {
    
    private int[] parent;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
        
        Arrays.sort(costs, Comparator.comparingInt((int[] o) -> o[2]));        
        
        for (int[] cost : costs) {
            if (findParent(cost[0]) == findParent(cost[1])) {
                continue;
            }
            
            answer += cost[2];
            unionParent(cost[0], cost[1]);
        }
        
        return answer;
    }
    
    public int findParent(int a) {
        if (parent[a] == a) {
            return parent[a] = a;
        }
        
        return parent[a] = findParent(parent[a]);
    }
    
    public void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
}