prim

🙋‍♂️ 들어가며

이번에는 prim에 대해 알아보자

가중치 (비용, 거리)가 나온다고 항상 헷갈리지말자

dijikstra -> 특정 노드까지 도달할때의 최소거리

prim -> 전체를 최소 비용으로 연결 (양방향 필수)

특징

prim은 오름차순을 하기 때문에 visited[]만 활용하면 되겠다 dijikstra처럼 값 비교가 필요 없겠다.

why? ->

어차피 정렬을 통해 작은값부터 나열하니까

거두절미하고 문제로 배워보자 (아래 링크 클릭)

섬 연결하기

✅ 코드

// prim
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;


class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        // 1. graph
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 2. 전체를 최소비용으로 순회 (prim) -> 양방향 
        for (int[] c : costs) {
            int cur_node = c[0];
            int cur_to = c[1];
            int cur_cost = c[2];
            graph[cur_node].add(new int[] {cur_to, cur_cost});
            graph[cur_to].add(new int[] {cur_node, cur_cost});
        }
        
        // 3. visited[]
        boolean[] visited = new boolean[n];
        
        // 4. pq -> 비용 오름차순 (작은 값부터 나열)
        PriorityQueue<int[]> pq = new PriorityQueue<> (
            (a,b) -> a[1] - b[1]
        );
        
        // 5. 시작점 삽입 (start_node, start_cost);
        pq.offer(new int[] {0, 0});
        
        // 6. prim
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cur_node = cur[0];
            int cur_cost = cur[1];
            
            // 6-1. 만약 방문했다면 skip
            if (visited[cur_node]) continue;
            
            // 6-2. 방문 안했다면 -> 방문
            visited[cur_node] = true;
            
            // 6-3. 값 추가 (어차피 오름차순이라 제일 작은것부터 순서대로 나열)
            answer += cur_cost;
            
            // 6-4. next_node
            for (int[] next : graph[cur_node]) {
                int next_node = next[0];
                int next_cost = next[1];
                
                // 6-5. 만약 next_node 방문 안했다면
                if (!visited[next_node]) {
                    pq.offer(new int[] {next_node, next_cost});
                }
            }
        }
        
        return answer;
    }
}