👀 문제
https://www.acmicpc.net/problem/16202
👊 도전
1. 설계
- PriorityQueue를 이용하여 MST를 만든다.
- 단, k번째는 weight가 낮은 k개들은 제거해야 한다.
- 그래프가 하나로 연결되어 있다면 weight를, 아니라면 0을 출력한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.util.*;
import java.io.*;
/**
* @author HEESOO
*
*/
class Main {
static int[] parent, rank;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
int m=Integer.parseInt(st.nextToken());
int k=Integer.parseInt(st.nextToken());
// Node들을 우선순위 큐에 삽입
PriorityQueue<Node> pq=new PriorityQueue<>();
for(int i=0;i<m;i++) {
st=new StringTokenizer(br.readLine());
pq.offer(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), i+1));
}
boolean flag=false;
for(int i=0;i<k;i++) {
if(flag) {// MST가 안되면 나머지 k번도 다 0
System.out.print("0 ");
continue;
}
int ret=getMSTweight(i, n, new PriorityQueue<>(pq));
if(ret==0) flag=true; // MST가 아님
System.out.print(ret+" "); // weight 출력
}
}
public static int getMSTweight(int k, int n, PriorityQueue<Node> pq) {
parent=new int[n+1]; // 최상위 부모
rank=new int[n+1]; // 레벨
for(int i=1;i<=n;i++) parent[i]=i;
int weight=0;
int cnt=0;
while(!pq.isEmpty()) {
if(k>0) { // 가중치가 작은 k개는 제거해야 함
k--;
pq.poll();
continue;
}
Node node=pq.poll();
int sParent=find(node.start);
int eParent=find(node.end);
if(sParent!=eParent) { // 최상위 부모가 다르다면(연결되어있지 않음)
union(sParent, eParent); // 연결
weight+=node.weight;
cnt++;
}
}
// MST가 되려면 n-1개의 간선이 있어야 함
if(cnt==n-1) return weight;
else return 0;
}
public static int find(int a) { // 최상위 부모 리턴
if(parent[a]==a) return a;
else return parent[a]=find(parent[a]);
}
public static void union(int a, int b) { // a와 b를 연결
// rank가 크다-> 트리 사이즈가 크다
// 큰거 밑에 작은게 들어간다
if(rank[a]>rank[b]) parent[b]=a;
else { // a보다 b 랭크가 큼
// b밑에 a가 들어감
parent[a]=b;
// 둘의 높이가 같다면 위에서 합쳤으니까 트리의 rank++
if(rank[a]==rank[b]) rank[b]++;
}
}
}
class Node implements Comparable<Node>{
int start;
int end;
int weight;
public Node(int s, int e, int w) {
this.start=s;
this.end=e;
this.weight=w;
}
@Override
public int compareTo(Node n1) {
return this.weight-n1.weight;
}
}
3. 결과
🤟 성공 🤟
트리가 하나로 연결되어있는지 체크하기 위해 parent에 같은 숫자로만 이루어져 있는지로 체크했는데 거기서 틀렸다.
6 5 1
1 4
3 4
2 5
2 6
4 6
일때 0이 나오기 때문이다. 정답은 15이다.
4. 설명
- PriorityQueue로 MST를 만든다
- pq는 weight가 작은 것이 더 큰 우선순위를 가진다.
- Node 클래스를 생성하여 시작, 끝 노드와 그 가중치를 넣는다. Override로 우선순위를 어떻게 해줄지 구현해야 한다.
- k번째이면 가중치가 작은 것 부터 k개를 제거하고 사용해야 한다. pq.poll()로 k개 만큼 빼준다.
- k개 이후부터는 node에 저장해서 start와 end의 최상위 부모가 같은지 확인한다. 같다면 이미 연결되어 있으므로 pass한다.
- 아니라면, union()으로 둘을 합친다.
- 합쳤으므로 이 가중치를 사용한다는 뜻이므로 weight에 누적한다.
- 또한, 간선 하나가 늘어난 것이므로 cnt++한다.
- n개의 노드로 그래프가 MST를 이루려면 간선은 n-1개 있어야 한다. 따라서 while문을 다 돌고 간선의 개수를 통해 하나의 그래프로 완성되었는지 확인한다.
- 맞다면 weight를, 아니라면 0을 리턴한다.