백준 1939 중량제한

문제

문제 분석

이전에 2585번 경비행기를 푼 경험이 있어서 그런지 그렇게 어렵진 않았다. 차라리 이걸 먼저 풀어보고 그걸 풀었으면 더 빠르게 풀 수 있지 않았을까 하는 아쉬움도 있었다.

이 문제 또한 파라매트릭 서치를 쓰는 문제였는데 DFS와 BFS만으로는 풀 수 없는 문제일까? 라는 생각때문에 한번 고민을 해봤었는데, 다음과 같은 이유 때문에 힘들것 같다고 느꼈다.

 

우선 조건에 대해서 살펴보면 O(N) = 10^4이고, 연결 그래프의 최댓값을 알기 위해서는 start_idx -> end_idx로의 모든 경로를 다 찾은다음에 비교하는 수 밖에 없기 때문에, 경로의 갯수는 O(N*M) = O(10^9) 까지도 될 수 있기 때문에 불가능한 경우가 생길 수 있을 것이다. 아마 BFS는 메모리 초과, DFS는 시간초과가 뜰 것 같다.

그렇기 때문에 일반적으로 우리가 일반적으로 DFS, BFS로 풀수 있는 문제에서는 N이 제한되어 있거나, 각 노드에 연결된 Children의 갯수(M)를 제한하면서 최악의 경우에 모든 점을 도는 것을 허용하도록 하는것..

 

대신 파라메트릭 서치를 활용하면 O(log(C) * N) 즉, 대충 O(3*10^8) 정도이므로 가능할 것이다.

그리고 파라메트릭 서치의 공통점은 일반적으로 결정문제로 전환하기 위해서 그림 전체를 보지 않고 노드 하나만 보는 경우가 많다고 느꼈다. 예를 들어 BFS문제는 뭐 최단경로, 합의 최소 이런 느낌이지만 파라메트릭 서치는 모든 노드가 어떤것을 만족하는 최솟값, 최댓값 이런 느낌인것 같다.

이렇게 되는 이유는 파라메트릭 서치 자체가 전체 문제를 판단문제로 나누는데, 이 판단문제를 해결하기 위해서 그렇게 각 노드에 대해서 만족시키려는가...보다! 

코드

#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<vector<pair<int,int>>> input_v;
int start_idx, end_idx;

bool is_possible(int parma_length)
{
    queue<int> q;
    q.push(start_idx);
    bool check_arr[10001] = {0};
    check_arr[start_idx] = 1;
    while(!q.empty())
    {
        int now_idx = q.front();
        q.pop();
        if(now_idx == end_idx)
            return true;
        for(int i=0; i<input_v[now_idx].size(); i++)
        {
            if(check_arr[input_v[now_idx][i].first] == 0 && input_v[now_idx][i].second >= parma_length)
            {
                check_arr[input_v[now_idx][i].first] = 1;
                q.push(input_v[now_idx][i].first);
            }
        }
    }
    return false;
}


void solution()
{
    // code
    int n,m;
    cin >> n >> m;
    for(int i=0; i<=n; i++)
    {
        vector<pair<int,int>> tmp_v;
        input_v.push_back(tmp_v);
    }
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        cin >> a >> b >> c; 
        input_v[a].push_back(make_pair(b,c));
        input_v[b].push_back(make_pair(a,c));
    }
    cin >> start_idx >> end_idx;
    int low = 0, high = 1000000001;
    int output = 0;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(is_possible(mid))
        {
            output = max(output, mid);
            low = mid + 1;
        }
        else
            high = mid - 1;
    }
    cout << output;
}

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

개선점?

다른 분들의 코드를 보니까 Edge를 크기별로 정렬한 후, disjoint set을 적용한다. 경로의 크기 순서대로 하나씩 선택하면서 경로를 구성하는 두 노드를 합치고, 그 결과 start_node와 end_node가 하나의 parent를 공유하면 연결되었다고 판단한다. 그리고 그 마지막 연결을 한 Edge가 연결을 위한 최댓값으로 판별하고 선택하는 출력하는 방식으로도 풀더라.

재밌는 풀이방식인것 같고, 조금더 그래프 이론쪽으로 파고들어도 좋을 것 같다