알고리즘/백준_JAVA
[JAVA] 4386. 별자리 만들기
happyAyun
2022. 2. 2. 19:32
별자리를 최소의 비용으로 만들기 위해 프림 알고리즘을 사용하였다.
우선 Node 클래스를 이용해 각 별의 자리를 배열로 놓고, Edge 클래스를 이용해 최소의 거리를 우선순위 큐를 이용해 구하였다.
마지막은 예시와 맞추기 위해 String.format("%.2f", result); 를 통해 형식을 맞추어 주었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
package algo;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class B_4386_별자리만들기 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
Node[] star = new Node[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
double fy = Double.parseDouble(st.nextToken());
double fx = Double.parseDouble(st.nextToken());
star[i] = new Node(fy, fx);
}
int cnt = 0;
double result = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>();
boolean[] visited = new boolean[N];
pq.offer(new Edge(0, 0)); // 시작
while (!pq.isEmpty()) {
Edge now = pq.poll();
if (visited[now.end])
continue;
visited[now.end] = true;
result += now.weight;
if (++cnt == N)
break;
for (int i = 0; i < N; i++) {
if (visited[i] || now.end == i)
continue;
double dist = Math
.sqrt(Math.pow(star[i].x - star[now.end].x, 2) + Math.pow(star[i].y - star[now.end].y, 2));
pq.offer(new Edge(i, dist));
}
}
System.out.println(String.format("%.2f", result));
// System.out.println(result); - 이렇게 해도 통과
}
static class Edge implements Comparable<Edge> {
int end;
double weight;
public Edge(int end, double weight) {
super();
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Double.compare(this.weight, o.weight);
}
}
static class Node {
double y, x;
public Node(double y, double x) {
super();
this.y = y;
this.x = x;
}
}
}
|
cs |