[백준][Java] 2585 - 경비행기

문제 정보

https://www.acmicpc.net/problem/2585

 

난이도 : G2

유형 : 이분탐색, BFS

---

문제 풀이

S에 T로 갈 때 연료 급료 횟수가 K이하가 되도록 최적의 연료통의 크기를 구하면 된다.

 

연료통의 크기에 따라 'K 이하로 도착할 수 있다' VS 'K 이하로 도착할 수 없다'

즉, 두 가지 경우가 발생하며 연료통의 크기에 따라 결과는 N, N , N,.... Y, Y Y 이런 형태가 나온다.

위의 형태에 따라 연료통의 크기는 이분탐색을 통해 찾아낼 수 있다.

 

이분탐색으로 얻은 연로통의 크기를 기준으로

시작점부터 시작하여 도착점까지 경유지를 포함하여 BFS 탐색을 진행하면 된다.

BFS 결과를 통해 매번 이분탐색으로 연로통의 크기를 조절하며 최적의 값을 찾을 때까지 BFS을 진행하면 된다.

 

BFS 탐색 시 이전에 방문했던 곳은 다시 방문하면 안 된다.

이전에 방문했던 곳을 다시 방문하면 연료를 더 소모하게 되니 꼭 방문 체크를 해주어야 한다.

 

시간복잡도는 O(N * log(시작점과 도착지까지 필요한 최대 연료 = 1415))

사실상 N * 10

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static final StringBuilder sb = new StringBuilder();
    public static StringTokenizer st;

    private int N;
    private int K;
    private List<Station> stations;

    private boolean check(int fuel) {
        Queue<int[]> que = new ArrayDeque<>();
        boolean[] isVisited = new boolean[N + 1];

        que.add(new int[]{0, 0}); // [현재 Station 인덱스, 급유지 방문 횟수]

        while (!que.isEmpty()) {
            int[] cur = que.poll();
            if (cur[1] > K) {
                continue;
            }

            if (fuel >= stations.get(cur[0]).getLiter(stations.get(N + 1))) {
                return true;
            }

            for (int i = 1; i <= N; i++) {
                if (isVisited[i]) { //탐색했던 곳을 다시 탐색하면 손해
                    continue;
                }

                int nextLiter = stations.get(cur[0]).getLiter(stations.get(i));

                if (nextLiter > fuel) {
                    continue;
                }

                isVisited[i] = true;
                que.add(new int[]{i, cur[1] + 1});
            }
        }
        return false;
    }

    private void solution() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        stations = new ArrayList<>();
        stations.add(new Station(0, 0));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            stations.add(new Station(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        stations.add(new Station(10000, 10000));

        int left = 1;
        int right = stations.get(0).getLiter(stations.get(N + 1)); //1415

        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        System.out.println(right);
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.solution();
    }

    static class Station {

        int x;
        int y;

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

        public int getLiter(Station station) {
            double distance = Math.sqrt(Math.pow(station.x - this.x, 2) + Math.pow(station.y - this.y, 2));
            if (distance % 1 != 0) {
                return (int) distance / 10 + 1;
            }
            return (int) distance / 10;
        }
    }

}