[백준]16202: MST 게임 - JAVA

[백준]16202: MST 게임

16202번: MST 게임

풀이

🪑 문제에서도 알 수 있듯이 MST문제였다. MST라는 것을 알려주지 않았 더라도 전형적인 MST문제이기 때문에 어렵지 않았을 것으로 예상되는 문제였다!

 

📝 문제를 정리해 보자!

• N개의 정점과 M개의 양방향 간선으로 이뤄진 그래프가 있다.
• K턴동안 진행되며 첫 턴에 MST를 구한다.
• 각 턴이 종료된 후 MST중에서 가중치가 가장 작은 간선을 제거한다.
• 나머지 간선으로 MST를 구할 수 있는지 확인한다.
• MST를 구할 수 없으면 0을 출력하고 구할 수 있으면 MST 비용을 출력한다.

 

 

🔧 문제를 풀어보자!

1. 입력받는 간선의 정보를 저장한다.
2. K번 동안 MST를 구한다.
3. MST를 구할 수 있다면 비용을 출력하고, 아니라면 0을 출력한다. 
4. MST에서 가장 작은 간선을 제거하고 다시 MST 구하기를 반복한다.

 

 

🔹 입력받는 간선의 정보를 저장한다.

• 우선순위 큐를 사용하여 입력 받는 간선의 정보를 저장한다.

 

 

🔹 K번 동안 MST를 구한다.

• KRUSKAL 알고리즘을 사용하여 MST를 구한다.
• 사용하는 간선의 정보는 다시 필요하므로 우선순위큐를 하나 더 만들어 사용한 간선을 다시 넣어준다.

 

 

🔹 MST를 구할 수 있다면 비용을 출력하고, 아니라면 0을 출력한다. 

• 일단 우선순위큐의 정보를 가지고 MST를 구한다.
• 구한 MST의 크기가 M-1개가 아니라면 MST를 구할 수 없다는 의미이므로 0을 출력해 주어야 한다. 이때 이후로도 계속 MST를 구할 수 없으므로 0을 남은 턴 만큼 반복한다.
• MST를 구할 수 있다면 비용을 출력한다.

 

 

🔹 MST에서 가장 작은 간선을 제거하고 다시 MST 구하기를 반복한다.

• 사용한 간선들을 넣어준 우선순위큐에서 가장 작은 간선을 제거해 주고, 해당 우선순위큐 내에서 MST를 찾는 것을 반복한다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    static PriorityQueue<Edge> mst;
    static int[] parent;
 
    public static void main(String[] args) throws IOException {
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
 
        for(int i = 1; i <= m; i++) {
            str = bf.readLine();
            st = new StringTokenizer(str);
            pq.offer(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), i));
        }
        //입력 끝
 
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < k; i++) {
            mst = new PriorityQueue<>();
            int[] result = kruskal(n);
            if(result[1] == n - 1) sb.append(result[0] + " ");
            else {
                sb.append("0 ".repeat(k - i));
                break;
            }
            mst.poll();
            pq = mst;
        }
        System.out.println(sb.toString());
    }
 
    public static int[] kruskal(int n) {
        int[] parent = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
        }
 
        int total = 0;
        int size = 0;
        while(!pq.isEmpty()) {
            Edge e = pq.poll();
            int p1 = find(e.n1, parent);
            int p2 = find(e.n2, parent);
            if(p1 != p2) {
                union(p1, p2, parent);
                total += e.cost;
                size++;
            }
            mst.offer(e);
        }
        return new int[] {total, size};
    }
 
    public static void union(int a, int b, int[] parent) {
        parent[a] = b;
    }
 
    public static int find(int n, int[] parent) {
        if(parent[n] == n) return n;
        else return parent[n] = find(parent[n], parent);
    }
 
    public static class Edge implements Comparable<Edge> {
        int n1, n2, cost;
 
        public Edge(int n1, int n2, int cost) {
            this.n1 = n1;
            this.n2 = n2;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Edge e) {
            return this.cost - e.cost;
        }
    }
}