https://www.acmicpc.net/problem/16398
1. 아이디어
행성을 노드, 플로우를 간선으로 하는 최소 스패닝 트리를 구하는 문제가 된다.
2. 문제풀이
크루스칼 알고리즘으로 최소 스패닝 트리를 구하는 방식으로 구현했다. 이때 N이 1이 될 수 있는 점과 가중치의 합이 int형 오버플로우가 발생할 수 있는 점에 주의해야했다.
3. 코드
import java.io.*;
import java.util.*;
public class Main {
private static class Edge implements Comparable<Edge> {
int a;
int b;
int w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}
private static int[] p;
private static int[] make(int N) {
int[] arr = new int[N];
for (int i = 1; i < N; i++) arr[i] = i;
return arr;
}
private static int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
private static void union(int x, int y) {
p[find(y)] = find(x);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
PriorityQueue<Edge> edges = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int w = Integer.parseInt(st.nextToken());
if (i < j) edges.add(new Edge(i, j, w));
}
}
long ans = kruskal(N, edges);
System.out.println(ans);
}
private static long kruskal(int N, PriorityQueue<Edge> edges) {
p = make(N);
long sum = 0;
int cnt = 0;
while (!edges.isEmpty()) {
Edge e = edges.remove();
if (find(e.a) == find(e.b)) continue;
union(e.a, e.b);
sum += e.w;
cnt++;
if (cnt == N - 1) return sum;
}
// N = 1인 경우 비용은 0
return 0;
}
}
4. 후기
'코딩테스트 준비 > 백준' 카테고리의 다른 글
[백준] 2146번 - 다리 만들기 [Java] (0) | 2025.02.11 |
---|---|
[백준] 2887번 - 행성 터널 [Java] (0) | 2025.02.11 |
[백준] 10423번 - 전기가 부족해 [Java] (0) | 2025.02.11 |
[백준] 1368번 - 물대기 [Java] (0) | 2025.02.11 |
[백준] 13418번 - 학교 탐방하기 [Java] (0) | 2025.02.11 |