[C++][백준 1939] 중량제한

[문제]

1939번: 중량제한 (acmicpc.net)

1939번: 중량제한

[문제 풀이]

파라메트릭 서치 + bfs를 이용한 문제.

* 나중에 다시 풀어보자. 파라메트릭 서치에 다른 알고리즘을 추가하니까 생각보다 구현단계에서 많이 막혔다.

10억과 1을 이용해서 binary search를 해서 몇이 나올 수 있는지 파악하는 문제.

파라메트릭 서치를 5문제 더 풀어보고 다시 풀어보자!

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int visited[100001];
int n,m;

vector<pair<int, int> > island[100001];

//파라메트릭 서치 + bfs
bool bfs(int sPosition, int ePosition, int mid){

    queue<int> truck;

    for(int i = 0;i<100001;i++){
        visited[i] = false;
    }

    truck.push(sPosition);
    visited[sPosition] = 1;

    while(truck.size() > 0){
        int curL = truck.front();
        truck.pop();

        if(curL == ePosition){
            return true;
        }

        for(int i = 0;i<island[curL].size();i++){
            int next = island[curL][i].first;
            int cost = island[curL][i].second;
            if(visited[next] == 0){
                if(mid <= cost){
                    visited[next] = 1;
                    truck.push(next);
                }
            }
        }
    }

    return false;
}

void parametric(int sPosition, int ePosition){
    int start = 1;
    int end = 1000000000;
    int mid;
    int result = 0;

    while(start <= end){
        mid = (start + end) / 2;
        if(bfs(sPosition,ePosition,mid) == true){
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
    }

    cout<<end<<endl;

    return;
}

int main() {
    cin>>n>>m;

    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        island[a].push_back(make_pair(b,c));
        island[b].push_back(make_pair(a,c));
    }

    int sPosition,ePosition;
    cin>>sPosition>>ePosition;

    parametric(sPosition,ePosition);

    return 0;
}