https://algospot.com/judge/problem/read/ARCTIC
algospot.com :: ARCTIC
남극 기지 문제 정보 문제 남극에는 N 개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. 탐사 본부가 다른 모든 기지에 연락을 할
algospot.com
N개의 탐사지점중 최소값으로 MST인 지점을 다 찾는지 문제.
이분탐색으로 시도했으나./.. 답이.. Prim으로 해결함..
이분탐색의 경우에는 예외케이스가 있나보다..
<Prim>으로 해결한 경우
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class arcrtic {
static int N;
static Pos[] PA;
static double[][] dis;
static ArrayList<Double> val;
static class Pos {
double x, y;
Pos(double x, double y) {
this.x = x;
this.y = y;
}
}
static double distance(Pos A, Pos B) {
return Math.sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/input_arctic.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine().trim());
for (int t = 1; t <= T ; t++) {
st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
PA = new Pos[N];
val = new ArrayList<>();
double x, y;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
x = Double.parseDouble(st.nextToken());
y = Double.parseDouble(st.nextToken());
PA[i] = new Pos(x, y);
dis = new double[N][N];
}
for (int i = 0; i < N-1 ; i++) {
for (int j = i+1; j < N ; j++) {
dis[i][j] = distance(PA[i], PA[j]);
dis[j][i] = dis[i][j];
val.add(dis[i][j]);
}
}
double max = prim();
System.out.println(String.format("%.2f", max));
}
}
static double prim() {
double max = -1;
boolean[] visit = new boolean[N];
Arrays.fill(visit, false);
Comparator<Pos> cmp = (o1, o2) -> Double.compare(o1.y,o2.y);
PriorityQueue<Pos> pq = new PriorityQueue<>(cmp);
for (int i = 0; i < N ; i++) pq.add(new Pos(i, dis[0][i]));
visit[0] = true;
Pos ps;
while (!pq.isEmpty()) {
ps = pq.poll();
if(visit[(int)ps.x]) continue;
visit[(int)ps.x] = true;
max = (max<ps.y)? ps.y:max;
for (int i = 0; i < N ; i++) {
if(!visit[i]){
pq.add(new Pos(i, dis[(int)ps.x][i]));
}
}
}
return max;
}
}
<이분탐색>
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class arcrtic {
static int N;
static Pos[] PA;
static double[][] dis;
static ArrayList<Double> val;
static class Pos {
double x, y;
Pos(double x, double y) {
this.x = x;
this.y = y;
}
}
static double distance(Pos A, Pos B) {
return Math.sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/input_arctic.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine().trim());
for (int t = 1; t <= T ; t++) {
st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
PA = new Pos[N];
val = new ArrayList<>();
double x, y;
double max = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
x = Double.parseDouble(st.nextToken());
y = Double.parseDouble(st.nextToken());
PA[i] = new Pos(x, y);
dis = new double[N][N];
}
for (int i = 0; i < N-1 ; i++) {
for (int j = i+1; j < N ; j++) {
dis[i][j] = distance(PA[i], PA[j]);
dis[j][i] = dis[i][j];
val.add(dis[i][j]);
}
}
Collections.sort(val);
int lo=0, hi = val.size()-1;
int mid = 0;
while (lo<hi) {
mid = (lo+hi)/2;
if(find(mid)) hi = mid;
else lo = mid + 1;
}
System.out.println(String.format("%.2f",val.get(mid)));
}
}
static boolean find(int mid) {
boolean[] visit = new boolean[N];
Arrays.fill(visit, false);
Queue<Integer> pq = new LinkedList<>();
pq.add(0);
int here;
int cnt = 0;
while (!pq.isEmpty()) {
here = pq.poll();
visit[here] = true;
cnt++;
for (int i = 0; i < N ; i++) {
if(!visit[i] && (dis[here][i]<=mid)) {
pq.add(i);
}
}
}
return cnt==N;
}
}