[문제해결을 위한 창의적 알고리즘] 경비행기 (고급, p232)
이 문제도 이분 탐색에 의한 결정 문제이다. 처음 문제를 보면서 해결 방법을 찾기란 쉽지 않을 수도 있지만, 이분 탐색 결정으로 푸는 해결 방법을 어느정도 머리속에 넣어 놓고 있으면, 풀만한 문제인 것 같다. 여기서는 자바로 구현하면서 스퀘어 루트 함수를 사용하지 않고 또한 큐도 사용하지 않고 구현해 보았다.
import java.util.Scanner;
public class LightFlightSol236 {
static class P{
public int x;
public int y;
}
public static int N;
public static int K;
public static int T;
// 시작점과 도착점을 제외하고 경유할 수 있는 비행장이 최대 1000개이므로, 1002개로 선언
public static int[] chk = new int[1002];
public static int[][] D = new int[1002][1002];
// 출발과 목적지 비행장 제외한 비행장수 10개이므로, 12개로 선언
public static P[] S = new P[12];
public static boolean f(int t){
// 큐를 간단하게 구현하는 방법으로 배열을 선언하고 시작 포인터와 끝 포인터를 관리한다.
// 비행장이 10개이고 이미 거친 비행장은 다시 가지 않는 것으로 할 것이므로 100개면 충분
int[] Q = new int[100];
int qs = 0;
int qe = 0;
for (int i = 0; i<1002; i++)
chk[i]=-1;
Q[qe]=0;
chk[0]=0;
qe++;
while (qe!=qs){
int i;
T = Q[qs];
qs++;
if (chk[T]>K+1)
return false;
else if (T==N+1)
return true;
for (i =0; i <= N+1; i++){
// 스퀘어 루트를 사용하지 않는 것이 계산 속도에 유리하므로 거리를 제곱한 값으로 비교
if (chk[i]==-1 &&D[T][i]<(t*10)*(t*10)) {
chk[i]=chk[T]+1;
Q[qe]=i;
qe++;
}
}
}
return false;
}
public static void main(String[] args){
int i, j, lb=0, ub=14142, m;
//, x, y;
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
S[0] = new P();
S[0].x =S[0].y=0;
S[N+1] = new P();
S[N+1].x=S[N+1].y=10000;
for (i =1; i<=N; i++){
S[i]=new P();
S[i].x=sc.nextInt();
S[i].y = sc.nextInt();
}
sc.close();
for (i=0; i <=N+1; i++)
for (j = 0; j<=N+1;j++)
// 스퀘어루트를 적용하지 않고 거리의 제곱값을 입력 거리 최대 값이 10000*10000 + 10000*10000 = 2억이므로 int에 담을 수 있다
D[i][j]=
(S[i].x-S[j].x)*(S[i].x-S[j].x) + (S[i].y-S[j].y)*(S[i].y-S[j].y);
while(lb<ub){
m=(ub+lb-1)/2;
if(f(m))
ub=m;
else
lb=m+1;
}
System.out.println(ub);
return;
}
}