[2585번] 경비행기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

2. 이분 탐색

이 문제는 BFS로 풀되 조금 신선한 문제에 해당하는 것 같다.

문제에서 봐야할 핵심은 다음과 같다.

최대 K번이니 K번 이하로 도착시킬 수 있다면 그때의 연료통의 최솟값을 계속해서 갱신해주면 된다.

이제 이분 탐색과 BFS를 어떻게 쓸지 생각해보자.

1. 이분 탐색은 당연히 연료통에 대해 적용시켜주면 된다.

K가 0일때 0,0 ~ 10000,10000에서 연료통 최대 범위는 1415이다.(필자는 그냥 1500으로 잡았다.)

따라서 이분 탐색의 시작과 끝은 start = 0, end = 1415로 잡으면 된다.

2. BFS는 어떻게 돌릴지 생각해보자.

K번 이하로 도착하면 되니, K번이 넘으면 당연히 continue를 해주면 되고,

현재 좌표에서 현재 연료통의 크기로 10000, 10000에 도착할 수 있다면 그 연료통과 현재 최소 연료통의 min을 갱신해주고,

이때 도착할 수 없다면, 자신과 인접한 중간 비행장들을 큐에 push해주면 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <memory.h>   using namespace std;   typedef pair<int, int> pii;   pii adj[1005]; bool visit[1005];   double getLength(int s, int e, int x, int y) {     return sqrt((s-x)*(s-x) + (e-y)*(e-y)) / 10; } int main() {     int n, k;     scanf("%d %d", &n, &k);       for (int i = 0; i < n; i++)     {         int x, y;         scanf("%d %d", &x, &y);         adj[i].first = x;         adj[i].second = y;     }       int start = 0;     int end = 1500;     int ans = 987654312;          while (start <= end)     {         int mid = (start + end) / 2;           bool once = false;           bool chk = true;           memset(visit, false, sizeof(visit));         queue<pair<pii, int> > q;           q.push({{ 0,0 }, k});                      while (!q.empty())         {             int x = q.front().first.first;             int y = q.front().first.second;             int cnt = q.front().second;               q.pop();                      if (cnt < 0)                 continue;               if (getLength(10000, 10000, x, y) <= (double)mid)             {                 once = true;                 break;             }             for (int i = 0; i < n; i++)             {                 int nx = adj[i].first;                 int ny = adj[i].second;                   if (visit[i])                     continue;                   if (getLength(nx, ny, x, y) <= (double)mid)                 {                     q.push({ { nx, ny}, cnt - 1 });                     visit[i] = true;                 }             }         }           if (once)         {             ans = min(ans, mid);             end = mid - 1;         }         else             start = mid + 1;     }       cout << ans << endl;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus