프림(Prim) 알고리즘

프림 알고리즘은 크루스칼 알고리즘과 마찬가지로 최소신장 트리를 만드는 알고리즘이다.

방법은

*모든 것은 minEdge[정점수]에 저장된다. //정점으로 가는 최소간선이라는 뜻

1. 임의의 정점 하나를 선택한다. 

2. 현재 정점에서 연결된 다른 정점으로의 간선이 더 짧으면 민엣지에 값을 갱신한다.

3. 2번을 계속 반복한다.

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

package practice2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

class info{
	int vertex,val;

	public info(int vertex, int val) {
		this.vertex = vertex;
		this.val = val;
	}
}

public class boj1197 {
	static int N, M, answer;
	static int minEdge[];
	static boolean visited[];
	static ArrayList<ArrayList<info>> list;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] s = in.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		
		visited = new boolean[N+1];//신장 트리에 포함여부
		minEdge = new int[N+1];
		
		list = new ArrayList<>();
		for(int i =0; i<=N;i++)list.add(new ArrayList<info>());
		
		for (int i = 0; i < M; i++) {
			s = in.readLine().split(" ");
			int from = Integer.parseInt(s[0]);
			int to = Integer.parseInt(s[1]);
			int val = Integer.parseInt(s[2]);
			list.get(from).add(new info(to,val));
			list.get(to).add(new info(from,val));
		}
		
		Arrays.fill(minEdge,Integer.MAX_VALUE);
		minEdge[1]=0;
		
		for(int c=0; c<N; c++) {
			int min =Integer.MAX_VALUE;
			int minVertex=-1;
			
			for(int i=1; i<=N;i++) {
				if(min>minEdge[i] && !visited[i]) {
					min = minEdge[i];
					minVertex =i;
				}
			}
			
			visited[minVertex]=true;//방문처리하고
			answer+=min;
			for(int i=0; i<list.get(minVertex).size(); i++) {
				int next =list.get(minVertex).get(i).vertex;
				int value =list.get(minVertex).get(i).val;//현재 선택된 정점에서 다음 정점으로 가는 비용
				if(minEdge[next] > value && !visited[next]) {
					minEdge[next] = value;
				}
			}
		}
		System.out.println(answer);
	}
}