프로그래머의 개발노트

[백준 2585] 경비행기 (C++) 본문

백준 알고리즘

[백준 2585] 경비행기 (C++)

7ULY 2021. 1. 17. 14:17


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


- 입력
첫 줄에는 n과 k가 하나의 공백을 사이에 두고 주어진다. 그 다음 n개의 줄에는 각 비행장 (급유지)의 정수좌표가 x y 형식으로 주어진다.

- 출력

S에서 T까지 k번 이하로 중간급유 하여 갈 수 있는 항로에서의 최소 연료통 용량에 해당되는 정수를 출력한다.

- 풀이

S와 T는 비행기가 무조건 지나가는 곳이라는 것을 생각하고 있어야 한다. S에서 시작 하여 갈 수 있는 곳은 사실상 모든 곳이다. 또한 모든 경유지에서 갈 수 있는 곳 또한 모든 곳이다. BFS를 통해 경유지를 몇 번 거쳤는지를 확인하고 k가 넘어간다면 해당 경유지는 가지 않는다. 이때 생각해볼 수 있는 것은, 한 경유지를 이미 들렸다면 다른 경유지에서 이미 들른 경유지를 갈 경우 어떤 경우가 더 짧은지에 대한 것이다. 하지만 잘 생각해보면, BFS를 통해 경유지를 먼저 점유하고 있기만 하다면 이미 그 경로가 최단 경로이다. 따라서 비행기가 갈 수 있는 좌표와 거리를 저장해 놓는다면, 최단 경로를 찾을 수 있다.

하지만 여기서 최단 경로를 찾기 위해서 거리를 정해놓는 것이 BFS의 base case로 들어가야 한다는 사실을 깨달을 것이다. 따라서 S에서 T까지의 거리를 max로 두고 최소 거리를 0으로 두고 binary search를 돌리면 된다. 난이도가 상당한 문제였다.

- 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
 
int n, k;
std::vector<std::pair<int, int> >oil_supply;
std::vector<bool> visited;
int oil_min, oil_max;
int b_mid, ans;
 
double cal_distance(int x1, int y1, int x2, int y2) // 거리 계산
{
    return(std::sqrt(std::pow((x2 - x1), 2) + std::pow((y2 - y1), 2)));
}
 
int cal_need_oil(size_t a, size_t b)
{
    int x1 = oil_supply[a].first;
    int y1 = oil_supply[a].second;
    int x2 = oil_supply[b].first;
    int y2 = oil_supply[b].second;
    int dis = static_cast<int>(std::ceil(cal_distance(x1, y1, x2, y2))); // 올림으로 계산
    // ex > 1000.001 이면 1001로 계산함.
    if (dis%10)
        return (dis/10 + 1);
    else
        return (dis/10);
}
 
bool bfs()
{
    std::queue<std::pair<int, int> >q; // cnt, now
    q.push(std::make_pair(0, 0));
    std::pair<int, int> a;
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        if (cal_need_oil(a.second, n+1) <= b_mid) // T 까지 거리가 b_mid 보다 작거나 같은 경우
            return (true);
        if (a.first > k) // 방문한 경유지의 수가 k보다 클 경우
            continue;
        for(size_t i = 1; i < static_cast<size_t>(n + 1); i++)
        {
            if (!visited[i] && cal_need_oil(a.second, i) <= b_mid)
            {
                visited[i] = true; // (bfs) 먼저 방문한 곳이 최단 경로이므로.(한 마디로 먼저 방문한 곳이 곧 cnt의 값이 최소)
                q.push(std::make_pair(a.first + 1, i));
            }
        }
    }
    return (false);
}
 
void binary_search(int b_min, int b_max)
{
    if (b_min > b_max)
        return ;
    b_mid = (b_min + b_max) / 2;
    visited = std::vector<bool>(n, false);
    if(bfs())
    {
        ans = b_mid;
        binary_search(b_min, b_mid - 1);
    }
    else
    {
        binary_search(b_mid + 1, b_max);
    }
}
 
void solve(void)
{
    binary_search(oil_min, oil_max);
}
 
void input_faster(void)
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
}
 
void input(void)
{
    input_faster();
    std::cin >> n >> k;
    oil_supply.resize(n+2);
    oil_supply[0].first = 0;
    oil_supply[0].second = 0;
    oil_supply[n+1].first = 10000;
    oil_supply[n+1].second = 10000;
    oil_max = 14150;
    oil_min = 0;
    for(size_t i = 1 ; i < static_cast<size_t>(n + 1) ; i++)
        std::cin >> oil_supply[i].first >> oil_supply[i].second;
}
 
int main(void)
{
    input();
    solve();
    std::cout << ans;
    return (0);
}
cs


저작자표시

'백준 알고리즘' 카테고리의 다른 글

[백준 17143] 낚시왕 (C++)  (0) 2021.01.20
[백준 1348] 주차장 (C++)  (0) 2021.01.17
[백준 9202] boggle (C++)  (0) 2021.01.17
[백준 1068] 트리 (python)  (0) 2020.07.05
[백준 2217] 로프 (python)  (1) 2020.05.14
'백준 알고리즘' Related Articles more
Comments