Programming/백준
[백준] 10423번 : 전기가 부족해
조용한고라니
2021. 3. 17. 22:58
반응형
10423번: 전기가 부족해
첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째
www.acmicpc.net
[크루스칼 알고리즘]
보통 MST하면 모든 정점이 하나의 덩어리로 연결되는 것을 생각할 수 있는데, 이 문제의 경우 발전소의 개수(k)개의 덩어리로 나뉘어 모든 정점이 연결되었을 때의 합을 출력하는 문제이다.
나는 유니온-파인드 부분을 수정했다. 보통 유니온-파인드는 두 정점 a, b를 받아 더 작은 번호를 부모 노드로 삼는 것이 일반적인데, Set에 발전소의 번호를 넣어두고
1) 두 정점 모두 발전소에 연결되어있지 않다면?
- 일반적인 유니온-파인드
2) 두 정점 중 한 곳에 발전소와 연결된 곳이 있다면?
- 부모노드의 번호는 그 발전소의 번호
3) 두 정점 모두 발전소에 연결되어있다면? (동일한 발전소든 서로 다른 발전소든 상관없이)
- 연결하지 않는다
코드로 보면 조금 더 이해가 쉬울 것이다.
static int[] parent = new int[1001];
static int getParent(int x){
if(parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
static boolean findParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(set.contains(a) && set.contains(b)) return true; //둘 다 발전소에 연결되어있으면 따로 연결할 필요 X
return a == b;
}
static void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(!set.contains(a) && !set.contains(b)){ //두 정점 모두 발전소와 떨어져있을 때
if(a < b)
parent[b] = a;
else
parent[a] = b;
}
//둘 중 한곳에 발전소와 연결되어있을 때
else if(set.contains(a) && !set.contains(b))
parent[b] = a;
else if(!set.contains(a) && set.contains(b))
parent[a] = b;
}
위의 Union-Find부분만 잘 이해한다면 나머지는 일반적인 크루스칼 알고리즘과 동일하다.
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Edge implements Comparable<Edge>{
int h, tg, d;
public Edge(int home, int target, int dist){
h=home;
tg=target;
d=dist;
}
@Override
public int compareTo(Edge o) {
return d - o.d;
}
}
static Set<Integer> set = new HashSet<>();
static List<Edge> list = new ArrayList<>();
static int[] parent = new int[1001];
static int getParent(int x){
if(parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
static boolean findParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(set.contains(a) && set.contains(b)) return true;
return a == b;
}
static void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(!set.contains(a) && !set.contains(b)){
if(a < b)
parent[b] = a;
else
parent[a] = b;
}
else if(set.contains(a) && !set.contains(b))
parent[b] = a;
else if(!set.contains(a) && set.contains(b))
parent[a] = b;
}
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());
for(int i=1; i<=n; i++) parent[i] = i;
st = new StringTokenizer(br.readLine());
for(int i=0; i<k; i++) set.add(Integer.parseInt(st.nextToken()));
for(int i=0; i<m; i++){
st = new StringTokenizer(br.readLine());
int h = Integer.parseInt(st.nextToken());
int tg = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
list.add(new Edge(h, tg, d));
list.add(new Edge(tg, h, d));
}
Collections.sort(list);
int sum = 0;
for(Edge e: list){
if(!findParent(e.h, e.tg)){
unionParent(e.h, e.tg);
sum += e.d;
}
}
System.out.println(sum);
}
}
반응형