최소 스패닝 트리

• PriorityQueue 을 사용하여 Prim을 구현
• pull 했을때 size가 0이 될때의 조건을 생각해주어야한다.(runtime error)

• class 객체 PriorityQueue 정렬하는 법

  PriorityQueue queue = new PriorityQueue<>(new Comparator<Node>() {
      @Override
      public int compare(Node o1, Node o2) {
        return o1.cost - o2.cost;
      }
    });
    
  객체 내에 있는 변수인 cost를 기준으로 자동 정렬한다.
  

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Comparator;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();

		PriorityQueue<Node>[] lists_E = new PriorityQueue[V + 1];

		for (int i = 1; i <= V; i++)
			lists_E[i] = new PriorityQueue<>(new Comparator<Node>() {
				@Override
				public int compare(Node o1, Node o2) {
					return o1.cost - o2.cost;
				}
			});

		for (int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int cost = sc.nextInt();
			lists_E[A].add(new Node(B, cost));
			lists_E[B].add(new Node(A, cost));
		}

		ArrayList<Integer> list = new ArrayList<>();
		boolean[] check = new boolean[V + 1];
		list.add(1);
		check[1] = true;
		int cnt = 1;
		long sum = 0;

		while (true) {
			// System.out.println(list);
			if (cnt == V)
				break;
			cnt++;
			int min = Integer.MAX_VALUE;
			int tmp = -1;
			for (int i = 0; i < list.size(); i++) {
				// System.out.println(list.get(i));
				while (lists_E[list.get(i)].size() > 0 && check[lists_E[list.get(i)].peek().save])
					lists_E[list.get(i)].poll();
				// System.out.println(" " + lists_E[list.get(i)].peek().save + " " +
				// lists_E[list.get(i)].peek().cost);
				if (lists_E[list.get(i)].size() > 0 && min > lists_E[list.get(i)].peek().cost) {
					tmp = list.get(i);
					min = lists_E[list.get(i)].peek().cost;
				}

			}
			Node node = lists_E[tmp].poll();
			list.add(node.save);
			sum += node.cost;
			// System.out.println("sum" + sum);
			check[node.save] = true;
		}
		System.out.println(sum);
	}

	static class Node {
		int save, cost;

		Node(int save, int cost) {
			this.save = save;
			this.cost = cost;
		}
	}
}