문제 풀이

0,0에서 10000, 10000으로 가야하는데 이분탐색으로 연료통의 용량을 정하고 정한 연료통의 용량을 토대로 bfs를 돌려 최대 k번을 경유할 때 10000, 10000로 갈 수 있는지 없는지를 파악을 한다.
현재 지점 x1, y1에서 x2, y2로 갈 때에 거리는

dis = (int)ceil(sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)));

필요한 연료는 dis를 10으로 나누었을때 나누어 떨어지면 dis /10, 아니라면 (dis / 10) + 1이다.
현재 지점에서 10000, 10000으로 이동가능하면 return true, 아니라면 경유지를 탐색하는데 경유지 까지 이동시 필요한 연료가 연료통의 용량보다 적어야 한다.

문제 링크

boj/2585

소스코드

PS/2585.cpp

#include <string>
#include <vector>
#include<iostream>
#include<limits.h>
#include <bitset>
#include<queue>
#include<map>
#include<memory.h>
#include<math.h>
using namespace std;

int bfs(int mid);
int n, k;
vector<pair<int, int>> v;
struct s
{
	int x;
	int y;
	int cur;
}typedef s;
int main()
{
	cin >> n >> k;
	v.push_back({ 0,0 });
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		v.push_back({ y,x });
	}
	int l = 0;
	int r = 987654321;
	int ans = 987654321;
	while (l <= r)
	{
		int mid = (l + r) / 2;

		if (bfs(mid))
		{
			r = mid - 1;
			ans = min(mid, ans);
		}
		else
			l = mid + 1;
	}
	cout << ans;
}

long get_oil(int x1, int y1, int x2, int y2)
{
	int  dis = (int)ceil(sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)));
	if (dis % 10 == 0)
		return dis / 10;
	else return dis / 10 + 1;
}
int bfs(int mid)
{
	queue<s> q;
	q.push({ 0,0,0 });
	bool visit[1001];
	memset(visit, 0, sizeof(visit));
	visit[0] = 1;
	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int cur = q.front().cur;

		q.pop();
		if (mid >= get_oil(x, y, 10000, 10000))
			return true;
		if (cur == k + 1)
			continue;
		for (int i = 1; i < v.size(); i++)
		{
			int nx = v[i].second;
			int ny = v[i].first;
			if (get_oil(x, y, nx, ny) <= mid && !visit[i])
			{
				visit[i] = 1;
				q.push({ nx,ny,cur + 1 });
			}
		}
	}
	return false;
}