백준 1939번 : 중량 제한

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

1939번: 중량제한

 문제 설명 

 

1.가중치가 있는 양방향 그래프가 주어짐.

2. 가중치는 다리가 버틸수있는 최대 무게이고 시작 점과 도착점이 주어졌을때, 한번에 가장많이 옮길수있는데 물품의       중량 출력

 

 알고리즘 

 

1.처음에는 다익스트라 알고리즘을 이용하여 이동시 드는 최소 가중치를 구하였는데 문제 의도와 는 달라서 fail.

2. 다음 블로그를 찾아보며 문제를 풀었다.  이문제의 해결방식은 bfs 와 이분 탐색을 이용하는것이다.진

3. 최대 중량을 이진탐색으로 탐색.

4. 다리위에서 최대  중량을 이용하여 시작점에서 도착점까지 이동가능 한경우를 bfs 로 탐색.

 

 

 코드 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int N, M;
 
int start, destination;
vector<pair<int, int>> V[100001];
int visited[100001];
 
bool BFS(int cost) {
    queue<int> q;
    q.push(start);
    visited[start] = 1;
 
    while (!q.empty()) {
        int  curr = q.front();
        q.pop();
 
        //목적지 까지 갈 수있다면 return true 
        if (curr == destination) return true;
 
        for (int i = 0; i < V[curr].size(); i++) {
            int next = V[curr][i].first;
            int next_cost = V[curr][i].second;
 
 
            //중량 제한이 cost 일때 다리를 건널 수있는 것 만 탐색
            if (!visited[next] && cost <= next_cost) {
                visited[next] = true;
                q.push(next);
            }
        }
 
    }
    //목적지까지 가지 못하면 return false;
    return false;
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int result = 0;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        //양방향 그래프 삽입
        V[a].push_back(make_pair(b, c));
        V[b].push_back(make_pair(a, c));
 
        result = max(result, c);
 
    }
 
    cin >> start >> destination;
 
 
 
    //이진 탐색
 
    int low = 0, high = result;
 
    while (low <= high) {
        //배열 초기화
        for (int i = 0; i <= N; i++)visited[i] = 0;
        int mid = (low + high) / 2;
 
        if (BFS(mid))
            low = mid + 1;
        else
            high = mid - 1;
 
    }
    cout << high;
}