[백준] 1922 - 네트워크 연결

[문제링크]

1922번: 네트워크 연결

 

0. 기초적인 MST 문제 (MST란?)

 

1. PRIM 알고리즘 사용, 최소 거리로 갈수있는 & 미방문한 노드 순서로 방문한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = pint(br.readLine());
		int M = pint(br.readLine());
		
		graph = new LinkedList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new LinkedList<>());
		}
		
		for (int i = 1; i <= M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int fst = pint(st.nextToken());
			int snd = pint(st.nextToken());
			int cost = pint(st.nextToken());
			
			graph.get(fst).add(new int[] {snd, cost});
			graph.get(snd).add(new int[] {fst, cost});
		}
		
		int totalCost=0;
		int start=1;//아무거나
		
		boolean[] isVisit=new boolean[N+1];//방문체크
		int[] cost = new int[N+1]; // 0번 PC는 없다
		Arrays.fill(cost, Integer.MAX_VALUE);
		cost[start]=0;//시작 cost 초기화
		
		for (int i = 0; i < N; i++) {
			
			int min=Integer.MAX_VALUE;
			int minNode=0;
			for (int j = 1; j <= N; j++) {
				if(!isVisit[j] && cost[j]<min) {
					min=cost[j];
					minNode=j;
				}
			}
			//가장 짧은거 연결
			isVisit[minNode]=true;
			totalCost+=min;
			
			//minNode 에서 연결되있는거 갱신
			int len = graph.get(minNode).size();
			for (int j = 0; j < len; j++) {
				int[] adjNode = graph.get(minNode).get(j);
				if(!isVisit[adjNode[0]]) {
					//방문한적 없다면
					cost[adjNode[0]] = Math.min(cost[adjNode[0]], adjNode[1]);
				}
			}
		}
		System.out.println(totalCost);
		
	}
	static LinkedList<LinkedList<int[]>>graph;
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면