백준 | 16202번. MST 게임 - 최소 신장 트리

⬛ 백준 16202번. MST 게임 - 최소 신장 트리

https://www.acmicpc.net/problem/16202

16202번: MST 게임

문제

N개의 정점과 M개의 양방향간선으로 이루어진 단순 그래프 G가 있다. 단순 그래프란, self-loop 간선(한 정점에서 자기 자신을 이어주는 간선)이 없고, 임의의 두 정점 사이 최대 한 개의 간선이 있는 그래프를 말한다. 단순 그래프의 스패닝 트리(Spanning Tree)는 다음 조건을 만족하는 간선의 집합이다.

1. 스패닝 트리를 구성하는 간선의 개수는 N-1개이다.
2. 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다.

스패닝 트리 중에서 간선의 가중치의 합이 최소인 것을 최소 스패닝 트리(Minimum Spanning Tree, MST)라고 부른다.

이제 그래프에서 MST 게임을 하려고 한다.

• MST 게임은 그래프에서 간선을 하나씩 제거하면서 MST의 비용을 구하는 게임이다. MST의 비용이란 MST를 이루고 있는 가중치의 합을 의미한다. 각 턴의 점수는 해당 턴에서 찾은 MST의 비용이 된다.
• 이 과정은 K턴에 걸쳐서 진행되며, 첫 턴에는 입력으로 주어진 그래프의 MST 비용을 구해야 한다.
• 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다.
• 한 번 제거된 간선은 이후의 턴에서 사용할 수 없다.
• 어떤 턴에서 MST를 만들 수 없다면, 그 턴의 점수는 0이다. 당연히 이후 모든 턴의 점수도 0점이다. 첫 턴에 MST를 만들 수 없는 경우도 있다.

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

입력

첫째 줄에 그래프 정점의 개수 N, 그래프 간선의 개수 M, 턴의 수 K가 주어진다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ min(10,000, N×(N-1)/2), 1 < K ≤ 100)

그 후 M개의 줄에 간선의 정보가 주어진다. 간선의 정보는 간선을 연결하는 두 정점의 번호 x, y로 이루어져 있다. 같은 간선이 여러 번 주어지는 경우는 없다. 간선의 가중치는 주어지는 순서대로 1, 2, ..., M이다.

정점의 번호는 1부터 N까지로 이루어져 있다.

출력

한 줄에 공백으로 구분하여 K개의 정수를 출력해야 한다. K개의 정수는 각 턴에 얻는 점수를 나타낸다.

힌트 설명

---

💚나의 풀이

• 처음에는 가중치가 입력으로 들어오지 않아서 어떻게 해야 하나 당황했다.
• 힌트를 보니, i번째로 입력 들어온 간선 정보 가중치가 i 가 된다는 걸 깨달았다.
• 그리고 총K번의 MST()를 호출하면서 주어진 간선들로 MST를 만들 수 있는지 확인해야 한다.
• PQ는 총 2개 만들었고, 실제 사용할 용도의 pQ 와 초기화 용도의 first를 따로 두었다.
• 총 k번의 MST() 를 호출한 뒤에는 ‘가장 작은 가중치 간선 하나를 제거해야 한다.’
• 제거한 상태의 큐를 다시 사용할 pQ에 세팅해준 뒤, mst()를 호출을 반복하면 정답이 나온다.

package to_1002_1;

import java.util.PriorityQueue;
import java.util.Scanner;

/*16202번. MST 게임 - 최소 신장 트리 */
class Edge implements Comparable<Edge>{
	int s, e, val;
	Edge(int s, int e, int val){
		this.s = s;
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int N, M, K;
	static int[] parent;//부모 
	static PriorityQueue<Edge> pQ = new PriorityQueue<>();
	static PriorityQueue<Edge> first;//초기화 용
	
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] =a;
		}
	}
	
	//MST
	static int[] MST() {
		
		//answer[0] : 비용 
		//answer[1] : 사용 간선 수
		int[] answer = new int[2];
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] = i;
		
		int useEdge = 0;
		int useCost = 0;
		
		while(!pQ.isEmpty()) { //빌 때까지 돌려야 함 
			Edge cur = pQ.poll();
			
			if(find(cur.s)  != find(cur.e)) {
				union(cur.s, cur.e);
				useCost += cur.val;
				useEdge++;
				
			}
			first.offer(cur);//하나씩 넘겨주잖아.
		}
		//답 세팅 
		answer[0] = useCost;//비용 
		answer[1] = useEdge; //개수 
		
		return answer;
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		N = kb.nextInt();
		M = kb.nextInt();
		K = kb.nextInt();
		
		//데이터 입력받기 
		for(int i=0; i<M; i++) { //M개 입력받기 
			int a = kb.nextInt();
			int b = kb.nextInt();
			//가중치는 i+1이다. 
			//양방향 간선
			pQ.offer(new Edge(a, b, i+1));
		}

		///K번 돌면서 답을 받아야 함
		for(int i=0; i<K; i++) {
			//매번 사용할 pQ는 초기화 해줌
			first = new PriorityQueue<>();//새로 생성해서 
			//pQ = first;//뺀 애를 다시 주입시킴 
			int[] result = MST();//하나씩 받기 
			if(result[1] == N-1) { //사용 간선이 N-1개 일 때 
				System.out.print(result[0] +" ");//그때의 가중치 합을 출력하고 
			}else {//그 외에는 무조건 0임 불가능하니까 
				System.out.print("0 ");
			}
			//매번 MST가 끝난 뒤에는 가장 최소 간선은 poll 처리 
			first.poll();//하나씩 뽑고 
			pQ = first;//뽑은 거를 넘겨주기 
		}	
	}
}