[백준/Baekjoon] 1939 중량제한 C++ :: Binary Search & BFS

https://www.acmicpc.net/problem/1939

1939번: 중량제한

---

1. Logic

다리가 버틸 수 있는 무게가 10억까지이기 때문에 택배의 무게를 이분탐색으로 찾아준다.

이분탐색의 Check함수는 택배의 무게인 mid보다 각 경로가 버틸 수 있는 무게가 크거나 같을 때만 통과시켜 입력받은 출발지에서 시작하여 도착지에 도달할 수 있으면 택배의 무게를 늘리고 도착하지 못하면 택배의 무게를 줄이면서 적절한 택배의 무게를 찾으면 된다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;
int n, m;
int s, e;

vector<pair<int, int>> input[100001];
int vis[100001];

bool check(int boxWeight) {
    memset(vis, false, sizeof(vis));
    queue<int> q;
    
    q.push(s);
    vis[s] = true;
    
    bool available = false;
    
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        
        if(cur == e) {
            available = true;
            break;
        }
            
        for(int i = 0; i < input[cur].size(); i++) {
            int next = input[cur][i].first;
            int ncost = input[cur][i].second;
                
            if(vis[next]) continue;
            if(boxWeight > ncost) continue;
            
            vis[next] = true;
            q.push(next);
        }
    }
    
    return available;
}

int binarySearch() {
    int start = 0;
    int end = INT_MAX;
    int mid;
    
    while(start + 1 < end) {
        int mid = (start + end) / 2;
        
        if(check(mid)) start = mid;
        else end = mid;
    }
    
    return start;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b, weight;
        cin >> a >> b >> weight;
        
        input[a].push_back({b, weight});
        input[b].push_back({a, weight});
    }
    
    cin >> s >> e;
    
    cout << binarySearch();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90