프림 알고리즘 (Prim Algorithm)

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
• 정점을 하나씩 선택할 때마다 간선을 추가하면서 트리 확장
• 두 종류의 상호배타집합 정보를 유지

           - 트리 정점들(tree-vertices) : MST를 만들기 위해 선택된 정점들

           - 비트리 정점들(non-tree vertices) : 선택 되지 않은 정점들

• 동작과정

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때까지 1, 2 과정을 반복

---

import java.util.Arrays;
import java.util.Scanner;

/*
7 11
0 1 2
0 2 2
0 5 8
1 2 1
1 3 19
2 5 5
3 4 7
3 5 11 
3 6 15
4 5 9
4 6 3
 */
public class Prim {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt(); // 정점의 개수
		int E = sc.nextInt(); // 간선의 개수
		int[][] adj = new int[V][V];
		// 간선의 정보를 입력 받는다.
		for(int i=0; i<E; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			adj[a][b] = c;
			adj[b][a] = c;
		}
		
		boolean[] check = new boolean[V];
		int[] key = new int[V]; // 현재 선택된 정점들로 부터 도달할 수 있는 최소거리
		int[] p = new int[V]; // 최소신장트리의 구조를 저장할 배열
		// key의 초기값은 무한대!
		Arrays.fill(key, Integer.MAX_VALUE);
		
		// 아무거나 하나 선택! (처음선택되는 친구가 루트이므로, 부모는 없는걸로, 거리가 0인걸로)
		p[0] = -1;
		key[0] = 0;
		
		// 이미 하나 골랐으니 나머지 V-1개를 골라보자.
		for(int i=0; i<V-1; i++) {
			int min = Integer.MAX_VALUE;
			int index = -1; // 찾으면 그놈의 위치를 여기에 저장.
			// 안골라진 친구들 중에서 key 가 가장 작은 친구를 뽑자.
			for(int j=0; j<V; j++) {
				// 일단 안골라진지 검사, key의 최솟값을 기억해야됨.
				if(!check[j] && key[j] < min) {
					index = j;
					min = key[j];
				}
			}
			// index : 선택이 안된 정점 중 key가 제일 작은 친구가 들어있다.
			check[index] = true;
			// index 정점에서 출발하는 모든 간선에 대해서 key를 업데이트
			for(int j=0; j<V; j++) {
				// check 가 안되어있으면서, 간선은 존재하고, 그 간선이 key보다 작다면, key값을 업데이트!!!
				if(!check[j] && adj[index][j] != 0 && key[j] > adj[index][j]) {
					p[j] = index;
					key[j] = adj[index][j];
				}
			}
		}
		int result = 0;
		
		for(int i=0; i < V; i++) {
			result += key[i];
		}
		System.out.println(result);
		System.out.println(Arrays.toString(p));
		
	}
}