064 : 최소 신장 트리 구하기

 

 

 

 

 

작은것부터 연결해야 하기 때문에

- 54321 정배열 PriorityQueue<Edge>

- 배열의 기준을 잡으려고(w) compareTo 필요

 

 

 

 

 

 

 

 

 

 

 

 

*

인식자에서 queue에 바로 넣어버리므로 별도 TP list는 필요하지 않음

 

(넣자마자 자동 정렬됨) 

 

 

 

 

 

 

union은 이미 check-in 되었다는 phaser로 사용됨

 

노드가 3개라면 모두 연결된 에지는 2(V-1)개이다

 

그래서 while공간이 1 > 2를 모두 순회하고 3은 진입하지 않는다

 

 

 

 

 

 

 

 

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    static int[] parent;
    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();

        // D2TP
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        parent = new int[V+1];
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }

        for (int i = 1; i <= E; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int w = sc.nextInt();
            pq.add(new Edge(s, e, w));
        }

        // OP
        int plate = 0;

            int used = 1;
            while (used < V) {
                Edge now = pq.poll();
                if (find(now.s) != find(now.e)) {
                    union(now.s, now.e);
                    plate += now.w;
                    used++;
                }
            }

        // OEC
        System.out.println(plate);
    }

    static int find(int a) {
        if (a == parent[a])
            return a;
        else
            return parent[a] = find(parent[a]);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b)
            parent[b] = a;
    }
}

class Edge implements Comparable<Edge> {

    int s;
    int e;
    int w;

    Edge(int s, int e, int w) {
        this.s = s;
        this.e = e;
        this.w = w;
    }

    @Override
    public int compareTo(Edge e) {
        return this.w - e.w;
    }
}