백준 1939 중량제한 (C++)

1939번: 중량제한

이분 탐색과 bfs를 이용한 문제이다. 입력 단위가 크기 때문에 bfs만을 사용하면 시간 초과가 발생한다. 그렇기에 이분 탐색을 이용해주었다. 0을 left, 10억을 right로 지정하고 가운데 값을 mid로 주어 반복문을 돌며 bfs를 돌려주었다. bfs는 mid가 cost가 되어 cost를 기준으로 더 큰 중량이 있다면 true, 없다면 false를 리턴하여 left와 right를 조정해주었다. 이 후 right를 출력해주었다. 어려웠던 문제였다. 처음에는 bfs만을 이용하여 실패를 했었고 후에 블로그를 참고하여 이분 탐색을 추가해주었다. 크루스칼 알고리즘을 통해서도 풀 수 있던 모양이다. 이러한 방식들을 잘 알아두어야 겠다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int N, M, f1, f2;
bool check[10001];
vector<pair<int, int>> v[10001];

bool bfs(int cost) {
    queue<int> q;

    check[f1] = true;
    q.push(f1);

    while (!q.empty()) {
        int now = q.front();

        if (now == f2) return true;

        q.pop();

        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i].first;
            int nw = v[now][i].second;

            if (check[next]) continue;
            if (cost > nw) continue;

            check[next] = true;
            q.push(next);
        }
    }

    return false;
}

void solution() {
    int left = 0, right = 1000000000;

    while (left <= right) {
        memset(check, false, sizeof(check));

        int mid = (left + right) / 2;
        if (bfs(mid)) left = mid + 1;
        else right = mid - 1;
    }

    cout << right;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

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

    cin >> f1 >> f2;

    solution();

    return 0;
}