[문제해결을 위한 창의적 알고리즘] 경비행기 (고급, 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;

}

}

Big O(N^2): 모든 비행장에 대해 도달할 수 있는 모든 비행장에 대해 계산

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/LightFlightSol236.java

문제해결을 위한 창의적 알고리즘 목록