[c++] 백준 #1939 중량제한 (190822)

< 풀이 > 

bfs + 이분 탐색 문제이다. 

0~w_max 사이의 중간 값으로 상한을 정한 후, bfs를 계속 돌면서 그 상한보다 더 큰 값의 edge만 지나갈 수 있게 한다. 그때 마지막 점에 도달가능한지 아닌지 확인해보면서 이 상한선을 estimate하면 된다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define MAX_N 100010

int N, M;
vector<ii> graph[MAX_N];
bool visited[MAX_N];
int start, fin;

bool bfs(int limit){
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        int len = graph[u].size();
        for(int i=0; i<len;i++){
            int v = graph[u][i].first;
            int w = graph[u][i].second;
            if (!visited[v] && limit <= w){
                if (v == fin) return true;
                visited[v] = true;
                q.push(v);
            }
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    int a, b, w;
    int w_max = -INF;
    for(int i=0; i<M;i++){
        cin >> a >> b >> w;
        graph[a].push_back(make_pair(b, w));
        graph[b].push_back(make_pair(a, w));
        w_max = max(w_max, w);
    }
    cin >> start >> fin;
    int low = 0, high = w_max;
    while(low <= high){
        memset(visited, false, sizeof(visited));
        int mid = (low + high)/2;
        bool ok = bfs(mid); // 도달 가능?
        if (ok) low = mid + 1; // 상한을 더 올려봄
        else high = mid - 1;
    }
    cout << high << '\n';
    return 0;
}