원더랜드(Prim)

원더랜드

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

입력 설명

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.

출력 설명

모든 도시를 연결하면서 드는 최소비용을 출려한다.

입력

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

출력

196

모범답안 참고 후 구현 코드

public class 원더랜드_프림 {
    static int[] unf;
    static int find(int v){
        if(v==unf[v]) return v;
        else return unf[v] = find(unf[v]);
    }
    static void union(int a, int b){
     int fa = find(a);
     int fb = find(b);
     if(fa!=fb) unf[a] = b;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt();
        int e = in.nextInt();

        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
        for(int i=0;i<=v;i++){
            graph.add(new ArrayList<Edge>());
        }

        int[] ch = new int[v+1];
        for(int i=0;i<e;i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            graph.get(a).add(new Edge(b,c)); //a에서 b로 가는 간선의 비용이 c
            graph.get(b).add(new Edge(a,c)); //b에서 a로 가는 간선의 비용이 c
        }

        int answer = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1,0));
        while(!pq.isEmpty()){
            Edge tmp = pq.poll();
            int ev = tmp.node; //도착 정점
            if(ch[ev] == 0){
                ch[ev] = 1;
                answer += tmp.cost;
                for(Edge ob : graph.get(ev)){ //
                    if(ch[ob.node]==0) pq.offer(new Edge(ob.node,ob.cost));
                }
            }
        }

        System.out.println(answer);

    }
    static class Edge implements Comparable<Edge> {
        @Override
        public int compareTo(Edge o){
            return this.cost -o.cost;
        }

        public Edge(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        int node;
        int cost;
    }
}

• 알고리즘

  PriorityQueue 사용
  pq.add(시작노드 간선 정보) -> 시작 노드 부터 탐색
  while(!pq.isEmpty())
  하나씩 빼면서 해당 노드의 ch값 확인 -> 0 일 경우 answer += edge.price계산
  해당 노드의 이웃 간선 정보 pq.add