[프로그래머스] LV 3 섬 연결하기

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

프로그래머스

접근 방법

1. 무방향 그래프가 주어지고, 그래프를 최소 가중치로 연결한 값을 구해야한다.
2. 최소 신장 트리(프림 or 크루스칼)로 풀 수 있다
3. 프림알고리즘을 설명해보자면 다음과 같다
   1. 임의의 정점을 선택해 최소신장트리(MST)에 추가한다. -> 해당 정점과 연결된 모든 간선을 우선순위큐에 추가
   2. cost를 기준으로 오름차순 정렬하는 우선선순위 큐에서 간선을 poll한다
   3. 만약 해당 간선이 MST에 포함된 두 정점을 연결한다면 Continue
   4. 그렇지않고 MST에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당 간선과 정점 v를 MST에 추가한다
   5. 정점 v와 MST에 포함되지 않은 정점을 연결하는 모든 간선을 우선순위 큐에 추가한다
   6. 2 ~ 5를 n-1개의 간선이 선택될때까지 반복한다

코드 (프림 알고리즘)

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
    	List<List<Node>> graph = new ArrayList<>(); 
        for(int i = 0 ; i < n ; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int[] c: costs){
            int s = c[0];
            int e = c[1];
            int w = c[2];
            
            graph.get(s).add(new Node(e,w));
            graph.get(e).add(new Node(s,w));
        }
        
        boolean[] isMST = new boolean[n];
        PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.w-o2.w);
        
        isMST[0] = true;
        for(Node node : graph.get(0)){
            pq.offer(node);
        }
        
        int cnt = 0;
        int ans = 0;
        while(cnt < n-1){
            Node cur = pq.poll();
            if(isMST[cur.e]) continue;
            
            ans+= cur.w;
            isMST[cur.e] = true;
            cnt++;
            for(Node node : graph.get(cur.e)){
                if(isMST[node.e]) continue;
                pq.offer(node);
            }
        }
        return ans;
    }
    class Node{
        int e,w;
        Node(int e,int w){
            this.e=e;
            this.w=w;
        }
    }
}