[JAVA/백준/2585] 경비행기

날짜	분류	번호	알고리즘 분류	링크
21-01-20	BOJ	2585	이분탐색&bfs	www.acmicpc.net/problem/2585

 

문제 요약

1. (0, 0)에서 (10000, 10000)까지 이동할 수 있는 최저의 연료통 용량 구하기
2. 단, 중간에 주유를 할 수 있는 횟수는 K번 이하여야 함
3. 참고사항
   • 연료의 단위는 1L이며 1L당 10km 비행 가능
   • 두 지점의 거리는 평면상의 거리임

 

풀이

1. (0, 0)에서 (10000, 10000)까지 필요한 연료량을 r(최대값)으로 두고 이분탐색 진행
2. mid로 목적지까지 도착할 수 있는지 없는지를 확인
   • bfs 사용
   • que에서 좌표를 하나 꺼내고 주어진 연료량으로 목적지까지 갈 수 있으면 true 반환
   • 목적지까지 갈 수 없는데 연료횟수가 K번이면 다음 좌표로 넘어감
   • 목적지 X 연료횟수도 X일 때, 모든 좌표에 대해서 방문X이고 주어진 연료량으로 갈 수 있는 좌표를 que에 삽입

 

비고

• 문제 읽다가 중단에 잠들었....zzZ

 

 

package b02.BOJ_2585_경비행기;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static Point[] station;
	static int N, K;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		station = new Point[N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			station[i] = new Point(x, y);
		}

		int l = 0, r = calcFuel(0, 0, 10000, 10000);
		while (l < r) {
			int mid = (l + r) / 2;
			if (canGo(mid)) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		System.out.println(l);
	}

	private static boolean canGo(int fuel) {
		boolean[] visit = new boolean[N];

		Queue<Point> que = new LinkedList<>();
		que.offer(new Point(0, 0, 0));

		while (!que.isEmpty()) {
			Point cur = que.poll();

			if (fuel >= calcFuel(cur.x, cur.y, 10000, 10000))
				return true;

			if (cur.cnt == K)
				continue;

			for (int i = 0; i < N; i++) {
				if (visit[i] || fuel < calcFuel(cur.x, cur.y, station[i].x, station[i].y))
					continue;
				visit[i] = true;
				que.offer(new Point(station[i].x, station[i].y, cur.cnt + 1));
			}
		}

		return false;
	}

	private static int calcFuel(int x1, int y1, int x2, int y2) {
		double result = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
		return result / 10 == ((int) result) / 10 ? (int) result / 10 : (int) result / 10 + 1;
	}

	static class Point {
		int x, y, cnt;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public Point(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}

	}

}