반응형
12-24 07:02
- Today
- Total
Link
개발하는 고라니
[백준] 1774번 : 우주신과의 교감 본문
반응형
[Kruskal Algorithm]
n개의 우주신과 황선자씨의 좌표를 받고, 각 n개의 정점에 대해 이중루프를 돌며 간선을 만들어준다. 이 때 하나의 정점 v는 n-1개의 간선을 갖는다.
만들어진 모든 간선 정보를 List에 담는다.
m개의 정점간 연결 정보를 받으며 주어진 정점들은 연결되었다고 parent 배열에 표기한다.
List를 정렬하고, 크루스칼 알고리즘을 통해 모든 정점을 연결한다.
# Code </>
public class Main {
static class Point{
int y, x;
public Point(int yy, int xx){
y=yy;
x=xx;
}
}
static class Edge implements Comparable<Edge>{
int h, tg;
double d;
public Edge(int home, int target, double dist){
h = home;
tg = target;
d = dist;
}
@Override
public int compareTo(Edge o) {
if(d > o.d) return 1;
else if(d < o.d) return -1;
return 0;
}
}
static List<Point> vList = new ArrayList<>();
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);
return a==b?true:false;
}
static void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
static double getDist(int y1, int x1, int y2, int x2){
return Math.sqrt( Math.pow(y1 - y2, 2.0) + Math.pow(x1 - x2, 2.0));
}
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());
for(int i=1; i<=n; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
vList.add(new Point(y, x));
parent[i] = i;
}
for(int i=1; i<=m; i++){
st = new StringTokenizer(br.readLine());
int home = Integer.parseInt(st.nextToken());
int target = Integer.parseInt(st.nextToken());
unionParent(home, target);
}
//간선 정보 생성 -> List에 담기
for(int i=0; i<vList.size(); i++){
Point p1 = vList.get(i);
for(int j=0; j< vList.size(); j++){
if(i == j) continue;
Point p2 = vList.get(j);
list.add(new Edge(i+1, j+1, getDist(p1.y, p1.x, p2.y, p2.x)));
}
}
Collections.sort(list);
double dist = 0.0;
for(Edge edge : list){
if(!findParent(edge.h, edge.tg)){
dist += edge.d;
unionParent(edge.h, edge.tg);
}
}
System.out.printf("%.2f\n", dist);
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 13023번 : ABCDE (0) | 2021.02.13 |
---|---|
[백준] 9376번 : 탈옥 (0) | 2021.02.13 |
[백준] 2638번 : 치즈 (0) | 2021.02.12 |
[백준] 1167번 : 트리의 지름 (0) | 2021.02.10 |
[백준] 16234번 : 인구 이동 (0) | 2021.02.09 |
Comments