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

문제 링크입니다. https://www.acmicpc.net/problem/1939

1939번: 중량제한

이분탐색을 활용해야하는 문제였습니다.

두 개의 섬이 주어졌을 때, 옮길 수 있는 중량의 최댓값을 구하는 문제입니다.

 

저는 이분탐색의 방법으로 풀었는데, 

low = 0, high = 다리의 최대 중량로 만들어, mid값을 얻은 뒤, mid값보다 큰 값으로만 두 섬을 이동할 수 있냐?

-> 해당 과정을 확인했습니다. mid 값보다 큰 값인 이유는 연결된 다리의 최솟값이 중량 제한이기 때문입니다.

 

이분 탐색이 끝났다면 중량제한이 high임으로 high를 출력하면 됐습니다.

 

BFS 코드는 전형적인 BFS 코드이니 보시면 이해하실 수 있을 것 같습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M;
vector<P> connect[10001];
int st, fin, maxi;
bool check[10001];

bool bfs(int cnt){
    queue<int> q;
    q.push(st);
    check[st] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(x == fin) return true;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int n_cost = connect[x][i].S;
            if(!check[xx] && n_cost >= cnt){
                check[xx] = true;
                q.push(xx);
            }
        }
    }
    return false;
}

void solve(){
    int low = 0, high = maxi;
    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;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y, cost;
        cin >> x >> y >> cost;
        connect[x].push_back({y, cost});
        connect[y].push_back({x, cost});
        maxi = max(maxi, cost);
    }
    cin >> st >> fin;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요