boj, 백준) 2585. 경비행기 ( C/ C++)

1. 문제 링크

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

2585번: 경비행기

2. 문제 개요

 경비행기가 출발지 S에서 목적지 T로 이동하고자 한다. 이때 연료통의 크기를 정하는 것이 중요한 문제가 된다.

급유를 받는 횟수가 k이하 일 때 연료통의 최소용량을 구하는 문제.

 

3. 문제 힌트

 Binary Search로 급유 없이 날아갈 수 있는 최대 거리를 'X'로 '결정'.

급유를 받는 최대 횟수 K로 입력받음.

 

급유 없이 날아갈 수 있는 최대 거리를 X로 하고 비행을 하는데

급유를 K번 초과하여 받는다? -> 급유를 많이 한다 -> 거리가 짧으니 많이한다 -> 거리를 늘여야 함.

급유를 K번 이하로 받는다? -> 급유가 적당함. -> 답을 기억해두고 최대 거리의 최솟값을 구해야 하니 거리를 줄여보자.

 

어떻게 이동하지? -> BFS

 

 

4. 문제 풀이

(3) 번을 보면 Binary Search 안에 BFS를 실행하므로 시간 복잡도는 대략 O(N^2 logN)이 될 것이다.  N이 최대 1000이므로 시간 초과는 나지 않을 것이다.

 

이 문제는 정점을 입력으로 받는다. BFS를 위해 이 정점들을 연결 그래프로 변경해줄 필요가 있다.

각 간선의 가중치는 문제에 주어진 거리 구하는 공식을 사용하여 구할 수 있고 연료 1L당 10km이므로

올림 처리 후 10으로 나눠줘야 한다.

 

그래프를 만들고 시작점을 기준으로 BFS를 실행한다.

조건은 다음 방문할 정점이 방문하지 않은 정점 이어야 하고, mid(최대 거리) 보다 같거나 짧은 거리여야 한다는 것이다.

BFS로 도착점까지 도착했으면 문제의 조건을 만족하는 답이고, 이 답의 최솟값을 구하기 위해 right = mid-1로 설정하여 재 실행한다. 도착점까지 도착하지 못했거나 급유를 많이 받았으면 연료통이 너무 작다는 의미이므로 left = mid +1을 해주어 이분 탐색을 이어나간다.

 

5. 코드

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

struct COORD {
	int x, y;
	int time;
};
COORD point[1002];
int dist[1002][1002];
int n, k;

double get_dist(COORD i, COORD j)
{
	return sqrt((j.x - i.x)*(j.x - i.x) + (j.y - i.y)*(j.y - i.y));
}
int main()
{
	scanf("%d %d", &n, &k);
	//point[0] = 출발점
	for (int i = 1; i <= n; ++i)
		scanf("%d %d", &point[i].x, &point[i].y);
	//point[n+1] = 종료점.
	point[n + 1].x = point[n + 1].y = 10000;
	//총 점은 n+2개. index는 0~n+1까지 사용.

	for (int i = 0; i < n+2; ++i)
	{
		for (int j = i + 1; j < n+2; ++j)
		{
			double d = get_dist(point[i], point[j]);
			int fuel = (int)ceil(d / 10.0);
			dist[i][j] = dist[j][i] = fuel;
		}
	}

	double d = get_dist(point[0], point[n+1]);
	int fuel = (int)ceil(d / 10.0);
	int left = 1, right = fuel;
	int ans = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;

		bool visited[1002] = { false };
		int count[1002];
		fill(count, count + n + 2, 987654321);
		pair<int, int> start = make_pair(0,0);
		//index, time
		//mid는 연료크기의 최대.

		queue<pair<int, int>> q;
		visited[0] = true;
		q.push(start);

		while (!q.empty())
		{
			pair<int,int> cur = q.front(); q.pop();
			count[cur.first] = cur.second;

			for (int i = 0; i < n + 2; ++i)
			{
				pair<int, int>next;
				next.first = i;
				next.second = cur.second + 1;

				if (visited[next.first] || dist[cur.first][next.first] > mid)
					continue;

				q.push(next);
				visited[next.first] = true;
			}
		}

		if (count[n + 1] - 1 > k)
		{
			left = mid + 1;
		}
		else
		{
			ans = mid;
			right = mid - 1;
		}
	}

	printf("%d", ans);
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~