Algorithm
[Algo] 백준 21924 도시 건설 JAVA
조핑구
2024. 5. 8. 13:58
문제 바로가기 : https://www.acmicpc.net/problem/21924
메모리 : 162984KB
시간 : 1196ms
언어 : Java 11
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static class Node {
int a, b, cost;
Node(int a, int b, int cost) {
this.a = a;
this.b = b;
this.cost = cost;
}
}
static PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.cost - o2.cost;
}
});
static int[] parent;
static long mini;
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
long all = 0;
mini = 0;
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
all += c;
pq.add(new Node(a, b, c));
}
if (kruskal()) {
System.out.println(all - mini);
} else {
System.out.println(-1);
}
}
private static boolean kruskal() {
int cnt = 0;
while (!pq.isEmpty()) {
Node n = pq.poll();
if (find(n.a) != find(n.b)) {
union(n.a, n.b);
mini += n.cost;
cnt++;
}
if (cnt == N - 1)
return true;
}
return false;
}
private static void union(int a, int b) {
int x = find(a);
int y = find(b);
if (x <= y) {
parent[y] = x;
} else if (x > y) {
parent[x] = y;
}
}
private static int find(int n) {
if (parent[n] == n)
return n;
else
return parent[n] = find(parent[n]);
}
}
크루스칼 문제. 크루스칼은 그리디알고리즘의 일종으로 그래프의 간선을 가중치의 오름차순으로 정렬해 놓은 뒤 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다. 정렬을 위해 Priority Queue를 사용한다. 사이클이 형성된다는 것은 불필요한 간선이라는 뜻이다. 우선순위 큐를 이용해 최소값끼리 이미 연결해놨으니 사이클이 형성되는 간선은 선택하면 안된다. 사이클을 판단하기 위해서 Union-Find를 활용한다. union은 정점을 묶어주는 함수이고, find는 해당 정점의 루트정점을 찾아주는 함수이다.