프림

package algo_0830;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class PrimTest2 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int V = Integer.parseInt(br.readLine()); // 정점의 수
		int[][] adjMatrix = new int[V][V];
		boolean[] visited = new boolean[V]; // 방문여부 배열(트리 포함 정점)
		int[] minEdge =  new int[V]; // 자신과 타정점들간의 간선비용 중 최소 간선 비용
		
		for(int i = 0; i < V; i++) {
			StringTokenizer st =  new StringTokenizer(br.readLine());
			for(int j = 0; j < V; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		Arrays.fill(minEdge, Integer.MAX_VALUE); // 최소값 갱신을 위해서 MAX값
		minEdge[0] = 0; // 0번 정점을 트리의 시작정점이 되도록 함(다른 정점이어도 상관 없음)
		int cost = 0;
		int i = 0;
		for(i = 0 ; i < V; i++) {
			// step 1. 트리 구성에 포함될 가장 유리한 정점 선택(비트리 정점 중 최소비용 간선의 정점 선택)
			int min = Integer.MAX_VALUE;
			int minVertex = -1;
			
			for(int j = 0; j < V; j++) {
				if(visited[j]) continue; 
				if(min > minEdge[j]) {
					minVertex = j;
					min = minEdge[j];
				}
			}
			
			if(minVertex == -1) break;
			visited[minVertex] = true;
			cost += min;
			
			// step 2. 선택된 정점과 타 정점들 간선비용 비교하기
			for(int j = 0; j < V; j++) {
				if(!visited[j] && adjMatrix[minVertex][j] > 0 && minEdge[j] > adjMatrix[minVertex][j]) {
					minEdge[j] = adjMatrix[minVertex][j];
				}
			}
		}
		int result = i == V ? cost : -1;
		System.out.println(result);

	}
}

/*
5
0 5 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0
*/