반응형
링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD
분류
그래프 탐색
트리
개인적 난이도
매우 쉬움 | 쉬움 | 보통 | 어려움 | 매우 어려움 |
핵심 알고리즘
각 섬들에 대해 이을 수 있는 모든 간선을 비용과 함게 최소 힙에 넣는다.
최소 힙에서 간선들을 저렴한 순서대로 하나씩 빼며 두 섬을 잇는다.
이 때 간선들이 사이클 구조를 이루지 않도록 하여야 한다.
사이클 구조 없이 N-1개의 간선을 연결하게 되면 반드시 N개의 섬은 이어진다.
사이클 구조를 피하기 위해서는 섬들의 부모섬(?)들을 기록해가며
이으려는 두 섬의 부모섬이 같은 경우 해당 간선은 버려야 한다.
그러므로 두 섬을 이을 때 섬의 부모를 잘 기록해 두어야 한다.
시행착오
없음
코드
import java.util.*;
import java.io.*;
class Solution{
static Map<Long, Integer> cache;
public static void main(String args[]) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc = 1; tc <= T; ++tc){
int N = Integer.parseInt(br.readLine());
int[] x = new int[N];
int[] y = new int[N];
String[] arr_x = br.readLine().split(" ");
String[] arr_y = br.readLine().split(" ");
double E = Double.parseDouble(br.readLine());
for (int i = 0; i < N; i++){
x[i] = Integer.parseInt(arr_x[i]);
y[i] = Integer.parseInt(arr_y[i]);
}
int[] parent = new int[N];
Queue<Line> lines = new PriorityQueue<Line>();
for (int i = 0; i < N; i++){
parent[i] = i;
for (int j = i + 1; j < N; j++){
lines.add(new Line(i, j, x[i], x[j], y[i], y[j]));
}
}
long sum = 0, cnt = 0;
while (!lines.isEmpty()){
Line l = lines.poll();
if (getParent(parent, l.to) == getParent(parent, l.from)) continue;
sum += l.len;
cnt++;
setParent(parent, l.to, l.from);
if (cnt == N - 1) break;
}
E *= sum;
System.out.println("#" + tc + " " + String.format("%.0f", E));
}
}
public static int getParent(int[] parent, int k){
while (k != parent[k]){
k = parent[k];
}
return k;
}
public static void setParent(int[] parent, int k, int newParent){
newParent = getParent(parent, newParent);
while (true){
int pk = parent[k];
parent[k] = newParent;
if (k == pk) break;
k = pk;
}
}
static class Line implements Comparable<Line>{
int from, to;
long len;
public Line(int from, int to, long x1, long x2, long y1, long y2){
this.from = from;
this.to = to;
this.len = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
public int compareTo(Line l){
if (this.len < l.len) return -1;
if (this.len > l.len) return 1;
return 0;
}
}
}
반응형
'알고리즘 > SW Expert Academy' 카테고리의 다른 글
1232. 사칙연산 (0) | 2022.02.16 |
---|---|
1233. 사칙연산 유효성 검사 (0) | 2022.02.16 |
1855. 영준이의 진짜 BFS (0) | 2022.02.16 |
1868. 파핑파핑 지뢰찾기 (0) | 2022.02.16 |
1767. 프로세서 연결하기 (0) | 2022.02.16 |