섬 연결하기

문제

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

코드

import java.util.*;

class Solution{
    class Node implements Comparable<Node>{
        int e;
        int w;
        public Node(int e, int w){
            this.e = e;
            this.w = w;
        }

        @Override
        public int compareTo(Node obj){
            if(this.w > obj.w)
                return 1;
            else if(this.w < obj.w)
                return -1;
            else
                return 0;
        }
    }

    public int solution(int n, int[][] costs) {
        int answer = 0;
        ArrayList<Node> g[] = new ArrayList[n];
        boolean check[] = new boolean[n];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(int i=0; i<g.length; i++)
            g[i] = new ArrayList<>();

        for(int[] cost : costs){
            g[cost[0]].add(new Node(cost[1], cost[2]));
            g[cost[1]].add(new Node(cost[0], cost[2]));
        }

        check[0] = true;
        for(Node node : g[0])
            pq.add(node);

        for(;!pq.isEmpty();){
            Node cur_node = pq.poll();
            if(check[cur_node.e])
                continue;
            answer += cur_node.w;
            check[cur_node.e] = true;
            for(Node node : g[cur_node.e]){
                pq.add(node);
            }
        }


        return answer;
    }
}

피드백

• MST 구하는 알고리즘인 프림 알고리즘을 구현했다.
  • 다이직스트라와 비슷했다.
• 나는 마지막 간선을 고르는 for문을 n-1로 했다가 안됬었다.
  • 간선은 n-1개만 존재하면 되는데 왜 안될까?
• 답은 현재 노드가 leaf node이면 간선이 없고, 따라서 1개의 간선을 여기서 산출하지 못하기 때문이다.
  • 즉, 모든 node가 간선을 새로 만들어 내지는 않기 때문
• 이 때문에 while()을 해서 모든 간선에 대해 check해서 구현해야함.