백준

[백준] 2585 경비행기 [자바]

거북이같은곰 2022. 1. 19. 22:48

 


https://hae-ong.tistory.com/39

 

백준 2585번 경비행기

경비행기 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 2025 683 436 31.322% 문제 경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때,

hae-ong.tistory.com

 


 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
class Node {
	int y;
	int x;
	Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int n, k;
	static ArrayList<Node> list = new ArrayList<>();
	static boolean[] xy;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 		n = Integer.parseInt(st.nextToken());
 		k = Integer.parseInt(st.nextToken());
 		
 		list.add(new Node(0,0));
 		for(int i = 0; i < n; i++) {
 			st = new StringTokenizer(br.readLine(), " ");
 			int a = Integer.parseInt(st.nextToken());
 			int b = Integer.parseInt(st.nextToken());
 			list.add(new Node(a, b));
 		}
 		int left = 0;
 		int right = 1500;
 		int result = 0;
 		while(left <= right) {
 			xy = new boolean[1001];
 			int mid = (left + right) / 2;
 			double a = mid * mid * 100;
 			if(bfs(a)) {
 				left = mid+1;
 			}
 			else {
 				right = mid-1;
 				result = mid;
 			}
 		}
 		System.out.println(result);
 	}
 	static boolean bfs(double dis) {
 		LinkedList<Integer> q = new LinkedList<>();
 		q.add(0);
 		int cnt = 0;
 		int size = 0;
 		double dis1;
 		double disto;
 		while(!q.isEmpty()) {
 			size = q.size();
 			if(cnt > k)
 				return true;
 			for(int i = 0; i < size; i++) {
 				int num = q.poll();
 				if(!xy[num]) {
 					xy[num] = true;
 					for(int j = 1; j <= n; j++) {
 						int tx = list.get(j).x-list.get(num).x;
 						int ty = list.get(j).y-list.get(num).y;
 						dis1 = Math.pow(tx, 2) + Math.pow(ty, 2);
 						if(dis1 <= dis) {
 							int rx = 10000-list.get(j).x;
 							int ry = 10000-list.get(j).y;
 							disto = Math.pow(rx, 2) + Math.pow(ry, 2);
 							if(disto <= dis) {
 								return false;
 							}
 							q.add(j);
 						}
 					}
 				}
 			}
 			cnt++;
 		}
 		return true;
 	}
}