백준 16202 - MST 게임

Java

16202 번 - MST 게임

문제

각 턴의 점수는 해당 턴에서 찾은 MST의 비용이 된다.

각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다.

양방향 간선으로 이루어진 단순 그래프와 K가 주어졌을 때, 각 턴의 점수가 몇 점인지 구하는 프로그램을 작성하시오.

접근 방법

매 턴마다 Prim 알고리즘으로 MST를 만들어 그 값을 출력한다.

MST를 만드는데 필요한 간선 중에 제일 비용이 작은 간선의 정보를 저장 한 다음, MST를 만들고 난 이후에 그 간선을 삭제한다.

MST를 만드는 과정에서 다음 노드를 선택할 수 없다면 0을 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, k, result;
	static int[][] graph;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	
    	graph = new int[n + 1][n + 1];
    	
    	int from, to;
    	for(int i = 1; i <= m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		from = stoi(stk.nextToken());
    		to = stoi(stk.nextToken());
    		graph[from][to] = i;
    		graph[to][from] = i;    		
    	}
    	
    	next : for(int i = 0; i < k; i++) {
    		// 삭제 할 간선을 찾는다.
    		int a = 0,b = 0;
    		int minVertex = Integer.MAX_VALUE;
    		
    		// -------- prim 알고리즘 -------------
    		int[] minNode = new int[n + 1];
    		boolean[] vis = new boolean[n+1];
    		Arrays.fill(minNode, Integer.MAX_VALUE);
    		result = 0;
    		int min, curN = 0;
    		minNode[1] = 0;
    		for(int j = 0; j < n; j++) {
    			min = Integer.MAX_VALUE;
    			for(int l = 1; l <= n; l++) {
    				if(!vis[l] && min > minNode[l]) {
    					curN = l;
    					min = minNode[l];
    				}
    			}
    			// 다음 노드를 찾을 수 없으면, MST를 만들 수 없다
    			if(min == Integer.MAX_VALUE) {
    				System.out.print(0 + " ");
    				continue next;
    			}
    			
    			vis[curN] = true;
    			result += min;
    			
    			for(int l = 1; l <= n; l++) {
    				if(!vis[l] && minNode[l] > graph[curN][l] && graph[curN][l] != 0) {
    					minNode[l] = graph[curN][l];
    					// 현재 MST에서 제일 작은 간선의 정보를 얻는다.
    					if(minVertex > graph[curN][l]) {
    						minVertex = graph[curN][l];
    						a = curN;
    						b = l;
    	    			}
    				}
    			}
    		}
    		// 제일 비용이 적은 간선 삭제
    		graph[a][b] = 0;
    		graph[b][a] = 0;
    		System.out.print(result + " ");
    	}
    	
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

없

개선할 점

없습니다.