이번에 풀어본 문제는
프로그래머스 섬 연결하기 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Edge {
    int n, cost;
    
    public Edge(int n, int cost) {
        this.n = n;
        this.cost = cost;
    }
}
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        List<List<Edge>> map = new ArrayList<>();
        
        for (int i = 0; i < n; i++) map.add(new ArrayList<>());
        
        for (int [] cost: costs) {
            map.get(cost[0]).add(new Edge(cost[1], cost[2]));
            map.get(cost[1]).add(new Edge(cost[0], cost[2]));
        }
        
        Edge start = new Edge(0, 0);
        Queue<Edge> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        q.add(start);
        boolean [] isSelected = new boolean[n];
        
        while (!q.isEmpty()) {
            Edge cur = q.poll();
            
            if (!isSelected[cur.n]) {
                isSelected[cur.n] = true;
                
                answer += cur.cost;
                
                for (Edge e: map.get(cur.n)) {
                    if (!isSelected[e.n]) q.add(e);
                }
            }
        }
        return answer;
    }
}

📝 풀이

MST를 구하는 문제입니다.
프림 알고리즘을 사용하여 스패닝 트리를 만들어 나가며, 그 과정에서 가중치 값을 누적해서 더해주면 해결할 수 있습니다.