[devmoon]프로그래머스 - (Java) 섬 연결하기

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

코딩테스트 연습 - 섬 연결하기

1. 유형

그리디

 

2. 시뮬레이션

 

이번 문제는 프림, 크루스칼을 사용하여 해결가능하다.

이전에 크루스칼을 사용했으니, 이번엔 프림을 사용한다.

testcase에 대한 시뮬레이션

 

아래도 마찬가지로 0,1번 노드와 연결된 가장 작은 간선을 선택

최종값은 아래와 같이된다.

 

3. 코드

import java.util.*;
class Solution {
    static PriorityQueue<int[]> pq;
    static List<int[]> list[];
    public int solution(int n, int[][] costs) {
        int answer = 0;
        list = new ArrayList[n];
        for(int i=0; i<n; i++)
            list[i]=new ArrayList<>();
        pq = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o, int[] o2){
                return o[1] - o2[1];
            }
        });
        for(int[] cost: costs){
            list[cost[0]].add(new int[]{cost[1], cost[2]});
            list[cost[1]].add(new int[]{cost[0], cost[2]});
        }
        boolean visited[] = new boolean[n];
        pq.add(new int[]{0,0});
        while(!pq.isEmpty()){
            int[] arr = pq.poll();
            if(visited[arr[0]]) continue;
            visited[arr[0]] = true;
            answer += arr[1];
            
            for(int node[]: list[arr[0]]){
                if(!visited[node[0]]){
                    pq.add(new int[]{node[0], node[1]});
                }
            }
        }
        return answer;
    }
}