섬 연결하기

문제 정보

• 프로그래머스 Lv.3
• 그리디
• 문제 링크

풀이

‘모든 노드를 연결하는 최소 비용’은 곧 최소 신장 트리(MST; Minimum Spanning Tree)를 구하는 문제다.

그렇기에 크루스칼 알고리즘, 혹은 프림 알고리즘을 사용하면 되는 문제다.

코드

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        Arrays.sort(costs, (a, b) -> Integer.compare(a[2], b[2]));
 
        int parent[] = new int[n];
        for (int i = 0; i < n; i++) 
            parent[i] = i;
        
        for (int[] cost : costs) {
            int fromParent = find(cost[0], parent);
            int toParent = find(cost[1], parent);
            
            if (fromParent == toParent)
                continue;
            
            parent[fromParent] = toParent;
            answer += cost[2];
        }
        
        return answer;
    }
    
    private int find(int i, int[] parent) {
        if (parent[i] == i)
            return i;
        
        return find(parent[i], parent);
    }
}

관련 노트

• 크루스칼 알고리즘
• 프림 알고리즘