백준 2585 경비행기, 파라매트릭 서치 심화

문제

문제 분석

개인적으로 접근 방법은 알겠는데 구현에 어려움이 있던 문제였다. 코테에 나왔다면 영락없이 바로 걸러졌을듯

이 문제의 요점은 최단거리가 아니라 [경로를 포함하는 간선 길이의 최댓값] 중 최솟값 을 찾는것이다 

우선 가장 먼저 접근했던 방법은 그리디 방식이었다.  그런데 접근 방식에 대해서 생각해보니 이치에 맞지 않았다

1번 가정 : 다음 점은 반드시 x+a, y+b 즉 점을 기준으로 1사분면에 존재할 것이다

 -> 지그재그와 같은 경로가 최적이라면 더 1사분면으로 가는 것이 더 손해일 수도 있다.

 2번 가정 : 하나의 길이를 정해두고 그 길이보다 반드시 큰 경로로만 갈 것이다.

 -> 말이 안됨 첫번째 선택한 길이 더 클 수도 있음, 길이는 의미가 없다.

 

결국에 생각하다 보니, 길이를 정해두고 그 길이에 대해서 K회 정차안에 도착할 수 있는가에 대해 접근하기 시작했다.

다행히 x와 y의 범위가 10^4로 비교적 크지 않았고, 이럴 경우 이분 탐색을 이용하여 log(N)의 탐색으로 정답을 찾을 수 있기 때문이다.

우선 그렇다면 이렇게 최대길이를 픽스해두고 그 길이에 대해 K회안에 정차할 수 있는지 없는지를 판별해야 하는데, 그 과정에서는 BFS를 사용했다.

Queue가 저장하는 Pair안에는 다음 인덱스와 지금까지 정차한 횟수를 저장하였고 이 정차횟수가 K+1이상일 때 혹은, Queue가 빈다면 탐색을 중지하는 방식으로 진행하였다.

이렇게 해서 K번 정차 이내에 마지막 점까지 도달한다면 그 연료통의 크기로는 탐색이 가능하다고 판단하고 이분탐색을 이용하여 다음 길이를 확인하는 것이다.

 

접근법 자체는 심플하지만 나는 이렇게 길이를 배열을 이용하여 미리 저장해두고 비교하는 방식을 이용하였기 때문에 이를 정의해주어야 했고, 마지막 점의 도착 여부를 체크하는 부분에서 언제 그만 탐색할지에 대해 판단하는 부분 등 부과적인 부분이 조금 까다로웠던것 같다.

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<list>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;

vector<pair<int,int>> input_v;
vector<vector<pair<int,double>>> edge; // [i][j].first는 연결된 위치, [i][j].second는 길이
int n, k;

double get_dist(int l_idx, int r_idx)
{
    double tmp_d = pow((input_v[l_idx].first - input_v[r_idx].first), 2) + pow((input_v[l_idx].second - input_v[r_idx].second), 2);
    return sqrt(tmp_d);
}


bool is_possible(int mid)
{
    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    int check_arr[10001] = {0};
    check_arr[0] = 1;
    while(!q.empty())
    {
        int now_count = q.front().first;
        int now_idx = q.front().second;
        if(now_count > k+1)
            break;

        q.pop();
        for(int i=0; i<edge[now_idx].size(); i++)
        {
            if(check_arr[edge[now_idx][i].first] == 0 && edge[now_idx][i].second <= mid)
            {
                check_arr[edge[now_idx][i].first] = now_count + 1;
                q.push(make_pair(now_count + 1, i));
            }
        }
    }
    if(check_arr[n+1] <= k+1 && check_arr[n+1] > 0)
        return true;
    else
        return false;
}

void solution()
{
    // code
    cin >> n >> k;
    vector<pair<int,double>> dummy_1;
    edge.push_back(dummy_1);
    input_v.push_back(make_pair(0,0));
    for(int i=0; i<n; i++)
    {
        vector<pair<int,double>> dummy_2;
        edge.push_back(dummy_2);
        int a, b;
        cin >> a >> b;
        input_v.push_back(make_pair(a,b));
    }
    vector<pair<int,double>> dummy_3;
    edge.push_back(dummy_3);
    input_v.push_back(make_pair(10000,10000));

    for(int i=0; i<input_v.size(); i++)
        for(int j=0; j<input_v.size(); j++)
            edge[i].push_back(make_pair(j,get_dist(i,j)));

    int low = 0;
    int high = 20000;
    int mid = (low + high) / 2;
    int output = MY_INT_MAX;
    while(low <= high)
    {
        int mid = (low + high)/2;
        if(is_possible(mid))
        {
            output = min(output, mid);
            high = mid-1;
        }
        else
            low = mid+1;
    }
    int last_output = output;
    if(last_output % 10 == 0)
        last_output = last_output / 10;
    else
        last_output = (last_output / 10) + 1;
    cout << last_output;
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

굳이 배열을 이용하여 비교하는 방식보다는 이렇게 범위가 작은 경우에는 그냥 거리를 직접적으로 연산하는 방식을 이용하는 편이 더 간결할 것 같다.

실제로 이 부분에서 구현하는 부분도 까다로웠지만, 이것을 사용하는 부분에서도 꼬이고 햇갈리면서 문제를 더 어렵게 만들었던것 같다.

조금 더 구조를 단순화 하고, 직접적인 코딩 전에 미리 pseudo코드를 이용하여 의도를 명확하게 하자