백준 경비행기 [c++]
2585 경비행기 골드2
문제
경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간에 내려서 급유를 받는 횟수가 적은 장점이 있지만 연료통의 무게로 인하여 속도가 느려지고, 안정성에도 문제가 있을 수 있다. 한편 작은 연료통을 장착하면 비행기의 속도가 빨라지는 장점이 있지만 중간에 내려서 급유를 받아야 하는 횟수가 많아지는 단점이 있다. 문제는 중간에 내려서 급유를 받는 횟수가 k이하 일 때 연료통의 최소용량을 구하는 것이다. 아래 예를 보자.
위 그림은 S, T와 7개의 중간 비행장의 위치를 나타내고 있는 그림이다. 위 예제에서 중간급유를 위한 착륙 허용 최대횟수 k=2라면 S-a-b-T로 가는 항로가 S-p-q-T로 가는 항로 보다 연료통이 작게 된다. 왜냐하면, S-p-q-T항로에서 q-T의 길이가 매우 길어서 이 구간을 위해서 상당히 큰 연료통이 필요하기 때문이다. 문제는 이와 같이 중간에 최대 K번 내려서 갈 수 있을 때 최소 연료통의 크기가 얼마인지를 결정하여 출력하면 된다. 참고사항은 다음과 같다.
모든 비행기는 두 지점 사이를 반드시 직선으로 날아간다. 거리의 단위는 ㎞이고 연료의 단위는 ℓ(리터)이다. 1ℓ당 비행거리는 10㎞이고 연료주입은 ℓ단위로 한다. 두 위치간의 거리는 평면상의 거리이다. 예를 들면, 두 점 g=(2,1)와 h=(37,43)간의 거리 d(g,h)는 (((\sqrt{(2-37)^2 + (1-43)^2}))) = 54.671… 이고 50＜d(g,h) ≤ 60이므로 필요한 연료는 6ℓ가 된다. 출발지 S의 좌표는 항상 (0,0)이고 목적지 T의 좌표는 (10000,10000)으로 모든 입력 데이터에서 고정되어 있다. 출발지와 목적지를 제외한 비행장의 수 n은 3 ≤ n ≤ 1000이고 그 좌표 값 (x,y)의 범위는 0＜x,y＜10000의 정수이다. 그리고 최대 허용 중간급유 횟수 k는 0 ≤ k ≤ 1000이다.
입력
첫 줄에는 n과 k가 하나의 공백을 사이에 두고 주어진다. 그 다음 n개의 줄에는 각 비행장 (급유지)의 정수좌표가 x y 형식으로 주어진다.
출력
S에서 T까지 k번 이하로 중간급유 하여 갈 수 있는 항로에서의 최소 연료통 용량에 해당되는 정수를 출력한다.
풀이
경비행기를 타고 목적지까지 이동하는데 K번 이하로 경유할 수 있는데, 경유지까지 내린 거리의 유클리드 거리의 ceil만큼의 연료탱크가 필요하다.
하나의 경로가 정해지면 경로에 대한 부분거리의 최대값의 ceil이 해당경로에 필요한 연료탱크값이 된다.
K이하 경유하는 경로 중 연료탱크값의 최소값을 찾는 문제이다.
각 지점인 N이 3 <= N <= 1000이고, K는 1 <= K <= 1000으로 단순 BFS를 하면, 1000개의 node에 대해 BFS를 해야하고(O(1000^2)) 이를 K가 1~1000까지 해야 하므로 제한시간안에 절대 불가능.
이분탐색을 사용해 연료탱크값을 추정하고(mid), mid값에 대해 bfs를 수행하면서 정해진 mid가 최소값이 될 수 있는지 확인할 수 있다.
시작점이 (0,0)이고 도착지점이 (10000,10000)이기 때문에 단일 부분경로의 최대값은 root(10000) 으로 대략 14100쯤 된다.
이분탐색을 하는데 log(14100) = 약 14, 여기에 bfs가 O(n^2)이므로 이분탐색을 이용해야 한다.
이분탐색에서 end값은 14100이상의 20000으로 설정하고 start는 0으로 설정한다. BFS결과가 true라면 최소값과 비교해 갱신한다.
BFS에서는 기본적으로 mid값보다 작은 distance를 가지는 점을 queue에 넣는다. 그리고 넣은 값이 mid보다 작다면 최소값일 가능성이 있으므로 true반환.
// in BFS(mid)
if(mid >= dist(x, y, 10000, 10000)){
return true;
}만약 이때까지 거친 경유지가 K보다 커지면 pop만하고 종료
if(kth == k + 1){
continue; //pop만
}이후 모든 지점들을 살펴보면서 (현재지점->다음지점)의 거리가 mid보다 작은 값들을 방문표시하고 queue에 삽입. (visited는 points에 대한것이라 1차원)
for(int i = 0; i < points.size(); i++)
{
int nx = points[i].first;
int ny = points[i].second;
if(mid >= dist(x, y, nx, ny) && !visited[i])
{
visited[i] = 1;
q.push(make_pair(make_pair(nx, ny),kth + 1));
}
}코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>
using namespace std;
int n, k;
vector<pair<int, int> > points;
int dist(int x1, int y1, int x2, int y2)
{
double x = x1 - x2;
double y = y1 - y2;
double dist;
dist = pow(x, 2) + pow(y, 2);
dist = sqrt(dist);
// cout << dist << endl;
return ceil(dist/10);
}
bool bfs(int mid)
{
queue<pair<pair<int, int>, int> > q;
bool visited[1001];
q.push(make_pair(make_pair(0,0),0));
memset(visited, 0, sizeof(visited));
// visited[0] = 1;
while(!q.empty())
{
int x = q.front().first.first;
int y = q.front().first.second;
int kth = q.front().second;
q.pop();
if(mid >= dist(x, y, 10000, 10000)){
return true;
}
if(kth == k + 1){
continue; //pop만
}
for(int i = 0; i < points.size(); i++)
{
int nx = points[i].first;
int ny = points[i].second;
if(mid >= dist(x, y, nx, ny) && !visited[i])
{
visited[i] = 1;
q.push(make_pair(make_pair(nx, ny),kth + 1));
}
}
}
return false;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
points.push_back(make_pair(x, y));
}
int start = 0;
int end = 20000;
int ans = 20000;
while(start <= end)
{
int mid = (end + start) / 2;
if(bfs(mid)){
end = mid - 1;
ans = min(ans, mid);
// cout << ans << endl;
} else{
start = mid + 1;
}
}
cout << ans << endl;
return 0;
}