백준 1939 / 중량제한

나중에 다시 한번 풀어볼 문제.

지금까지 풀어온 단순한 BFS 문제들과는 달리,

BFS와 이진 탐색을 함께 사용하여야 되는 문제다.

섬의 개수와 다리의 개수가 굉장히 많고, 중량의 최대한계도 높기때문에 일반적인 BFS로 풀면 시간초과 / 메모리초과가 나기 떄문이다.

풀이법은 

시작부터 중량 X를 실고 출발한다고 가정

목표 섬에 도착하면 X를 높이고,

목표 섬에 도착하지 못하면 X를 낮추는 방식으로 푼다.

코드 (80~90번째 줄이 핵심이다.)

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<tuple>
#include<memory.h>
 
using namespace std;
 
bool check[10001];
vector<vector<int>>arr;
vector<vector<int>>cost;
vector<int>ans;
 
int maxcost = 0;
int start, goal;
 
bool bfs(int nowcost) {
 
    queue<int>q;
    q.push(start);
    check[start] = true;
 
 
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        if (now == goal) {
            return true;
        }
 
        for (int i = 0; i < arr[now].size(); i++) {
            int to = arr[now][i];
            int limit = cost[now][i];
            
            if (check[to] == false && nowcost <= limit) {
                check[to] = true;
                q.push(to);
            }
        }
    }
 
 
 
    return false;
 
}
int main() {
    //freopen("Text.txt", "r", stdin);
 
    int n, m;
    cin >> n >> m;
 
    arr.resize(n + 1);
    cost.resize(n + 1);
 
    for (int i = 0; i < m; i++) {
        int a, b;
        int c;
 
        scanf("%d %d %d", &a, &b, &c);
 
        arr[a].push_back(b);
        cost[a].push_back(c);
        arr[b].push_back(a);
        cost[b].push_back(c);
 
        maxcost = max(maxcost, c);
 
    }
 
    cin >> start >> goal;
 
    int low = 0;
    int high = maxcost;
 
 
    while (low <= high) {
        memset(check, false, sizeof(check));
 
        int mid = (low + high) / 2;
 
        if (bfs(mid)) {
            low = mid + 1;
        }
        else
            high = mid - 1;
    }
 
 
    cout << high;
    
 
}