[백준/BOJ] 백준 2585번 : 경비행기

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

2585번: 경비행기

 

이분 탐색을 이용해 특정 용량의 연료통일 때, k번 이하의 급유로 출발지에서 목적지까지 갈 수 있는지 확인하는 방법으로 k번 이하의 급유에서 출발지에서 목적지로 가는 연료통의 최소 용량을 구했다.

 

특정 용량으로 k번 이하로 급유해서 출발지에서 목적지까지 갈 수 있는지 확인하는 방법은, 출발지에서 너비 우선 탐색 같은 방식으로 목적지까지 탐색하는 과정을 거쳐 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

int n, k;
vector<pair<int, int>> points;
pair<int, int> start = make_pair(0, 0);
pair<int, int> dest = make_pair(10000, 10000);

//해당 연료통으로 k번 이하 급유해서 start에서 dest까지 갈 수 있는지 확인
bool check(int oil) {

	vector<int> discovered(n + 1, 0);
	queue<pair<pair<int, int>, int>> q; //((위치),중간 급유한 횟수))

	q.push(make_pair(start, 0));

	while (!q.empty()) {
		pair<int, int> here = q.front().first;
		int cnt = q.front().second;
		q.pop();

		//목적지에 도착 했을 때
		if (here == dest) {
			return true;
		}

		for (int i = 0; i < n + 1; i++) {
			pair<int, int> there = points[i];

			if (discovered[i] == 0) {
				//here에서 there로 갈 수 있는지 확인
				if (ceil(sqrt(pow(there.first - here.first, 2) + pow(there.second - here.second, 2))) <= (double)(oil * 10)) {

					//만약 there가 dest도 아닌떼 cnt+1이 k를 넘길때
					if (there != dest && cnt + 1 > k) {
						continue;
					}

					discovered[i] = 1;
					q.push(make_pair(there, cnt + 1));
				}

			}
		}
	}

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;

		points.push_back(make_pair(x, y));
	}
	points.push_back(dest);

	//k번 이하의 급유로 mid 연료통일때 start에서 dest까지 갈 수 있는지 확인
	int left = 0;
	int right = 1415; //sqrt(200,000,000) = 14142.~ => 한번도 중간급유 안하고 가려면 연료통의 크기는 최소 1415 리터 필요
	int result = -1;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (check(mid)) {
			result = mid;
			right = mid - 1;
		}

		else {
			left = mid + 1;
		}

	}

	cout << result;

	return 0;
}