[Baekjoon Online Judge] 백준 2585번 경비행기(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2585번 경비행기

(C++, Python)

(글쓴날 : 2020.04.09)

 

---

* Baekjoon Online Judge, 백준 2585번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2585번 경비행기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2585

2585번: 경비행기

---

2) 풀이 과정

좌표 평면상에 비행기의 급유를 위한 중간 비행장들의 위치와 착륙 허용 횟수가 주어질 때, 출발지 (0, 0)에서 목적지 (10000, 10000)까지 비행기를 타고 가는데 필요한 최소 연료통의 용량을 구하는 문제입니다.

거리의 단위는 km이며, 이동할 두 위치 간의 거리는 두 점 사이의 거리 공식을 적용한 수치로 계산합니다.

단, 연료는 10km당 1리터를 소모합니다.

 

저의 경우, 이분 탐색과 BFS를 적용하여 문제에 접근했으며, mid 값을 연료통의 용량으로 설정하여 이분 탐색을 하였습니다.

이분 탐색을 통해 얻어지는 mid 값을 BFS() 함수에 넘겨 너비 우선 탐색을 실시했고, 큐의 크기를 레벨마다 측정해 깊이가 깊어질 때마다 착륙 허용 횟수를 초과했는지 항상 체크했습니다.

그렇게 탐색을 반복하여, 착륙 허용 횟수 안에 목적지에 도착한 연료통의 용량을 구했고 최종적으로 최소 연료통 용량을 출력하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <cmath>
 
using namespace std;
 
int n, k;
bool visit[1001];
 
bool BFS(const vector<pair<int, int>> &airport, int vertex, int fuel)
{
    memset(visit, false, sizeof(visit));
    int landingCount = 0;
    int arrivedVertex = 0;
    double distance = 0.0;
    double distanceForDestination = 0.0;
    int qSize = 0;
    queue<int> q;
    q.push(vertex);
 
    while (!q.empty())
    {
        if (landingCount > k)
            return false;
 
        qSize = q.size();
        for (int i = 0; i < qSize; i++)
        {
            arrivedVertex = q.front();
            q.pop();
 
            if (!visit[arrivedVertex])
            {
                visit[arrivedVertex] = true;
 
                for (int j = 1; j < n + 1; j++)
                {
                    distance = sqrt(pow(airport[arrivedVertex].first - airport[j].first, 2) + pow(airport[arrivedVertex].second - airport[j].second, 2));
 
                    if (distance <= fuel)
                    {
                        distanceForDestination = sqrt(pow(10000 - airport[j].first, 2) + pow(10000 - airport[j].second, 2));
 
                        if (distanceForDestination <= fuel)
                            return true;
 
                        q.push(j);
                    }
                }
            }
        }
 
        landingCount++;
    }
 
    return false;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    vector<pair<int, int>> airport(n + 1, make_pair(0, 0));
    for (int i = 1; i < n + 1; i++)
        cin >> airport[i].first >> airport[i].second;
 
    int left = 0;
    int right = 10000;
    int mid = 0;
    int result = 0;
 
    while (left <= right)
    {
        mid = (left + right) / 2;
 
        if (BFS(airport, 0, mid * 10))
        {
            result = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
 
    cout << result;
 
    return 0;
}

---

* Python 코드(PyPy3)

from collections import deque
import sys, math
input = sys.stdin.readline
 
n, k = map(int, input().split())
airport = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]
 
 
def BFS(vertex, fuel):
    visit = [False] * (n + 1)
    landingCount = 0
    dq = deque()
    dq.append(vertex)
 
    while len(dq):
        if landingCount > k:
            return False
        
        for _ in range(len(dq)):
            vertex = dq.popleft()
 
            if not visit[vertex]:
                visit[vertex] = True
 
                for i in range(1, n + 1):
                    distance = math.sqrt(pow(airport[vertex][0] - airport[i][0], 2) + pow(airport[vertex][1] - airport[i][1], 2))
 
                    if distance <= fuel:
                        distanceForDestination = math.sqrt(pow(10000 - airport[i][0], 2) + pow(10000 - airport[i][1], 2))
 
                        if distanceForDestination <= fuel:        
                            return True
                        
                        dq.append(i)
 
        landingCount += 1
    
    return False
 
 
left = 0
right = 10000
result = 0
 
while left <= right:
    mid = (left + right) // 2
 
    if BFS(0, mid * 10):
        result = mid
        right = mid - 1
    else:
        left = mid + 1
 
print(result)

---