백준 16202 - MST게임

백준 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 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 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); } }

from http://moons-memo.tistory.com/241 by ccl(A) rewrite - 2021-09-09 00:00:33