백준 16202 - MST게임

[문제 바로가기]

 

1. 유형

MST

 

2. 문제 분석

2-1. 해설

크루스 칼 알고리즘을 여러 번 사용해서 푸는 문제입니다.

크루스 칼을 한번 돌리고, 가중치가 가장 작은 선분을 하나 빼고, 다시 크루스 칼 돌리고...

이걸 반복해주면 끝나는 문제였습니다.

 

2-2. 설계

3. 코드

부노노드가 전부 같은지 확인하는 코드

 

부모 노드가 같지 않으면 union을 사용해서 부모 노드 동일하게 만들어줌

 

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

public class Main {
	static int N, M, K, parent[];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		List<int[]> list = new ArrayList<>();
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		K = stoi(st.nextToken());
		parent = new int[N + 1];

		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(in.readLine());
			int a = stoi(st.nextToken());
			int b = stoi(st.nextToken());
			list.add(new int[] { a, b, i });
		}
		Collections.sort(list, (a, b) -> (a[2] - b[2]));
		int start = 0;
		int ans[] = new int[K];
		while (start < K) {
			Queue<int[]> pq = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
			init();
			for (int i = start; i < M; i++) {
				int cur[] = list.get(i);
				pq.add(cur);
			}
			int total = 0;
			while (!pq.isEmpty()) {
				int cur[] = pq.poll();
				if (find(cur[0]) != find(cur[1])) {
					union(cur[0], cur[1]);
					total += cur[2];
				}
			}
			if (check()) {
				ans[start] = total;
				start++;
			} else
				break;
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < K; i++) {
			sb.append(ans[i]).append(" ");
		}
		System.out.println(sb);
	}

	static int find(int x) {
		if (x == parent[x]) {
			return x;
		}
		return parent[x] = find(parent[x]);
	}

	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a < b) {
			parent[b] = a;
		} else {
			parent[a] = b;
		}
	}

	static boolean check() {
		for (int i = 1; i < N; i++) {
			if (find(i) != find(i + 1)) {
				return false;
			}
		}
		return true;
	}

	static void init() {
		for (int i = 1; i <= N; i++) {
			parent[i] = i;
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}