백준 1939 - 중량 제한

문제

 

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

1939번: 중량제한

 

 

풀이

 

그래프 탐색과 이분 탐색을 이용해서 해결하는 문제이다. 이분 탐색을 통해 중량 값을 찾고, 그래프 탐색을 통해 해당 중량 값으로 끝 지점까지 도달할 수 있는지 파악하면 된다.

 

1. 중량 값이 1부터 10억까지 가능하므로 이분 탐색을 통해 mid 값을 찾는다.

2. 해당 mid 값을 이용해서 그래프 탐색을 통해 시작 지점부터 끝 지점까지 탐색을 해본다.

2.1. 탐색이 성공하면 left = mid + 1로 설정하고 다시 이분 탐색을 한다.

2.2. 탐색에 실패하면 right = mid - 1로 설정하고 다시 이분 탐색을 한다.

3. 탐색에 성공하면 중량의 최대값을 갱신해준다. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
 
using namespace std;
 
int N, M;
int A, B, C;
int from, to;
vector<pair<int, int>> graph[10001];
bool visit[10001];
int result;
 
bool bfs(int w)
{
    queue<int> q;
    visit[from] = true;
    q.push(from);
 
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
 
        if (cur == to) return true;
 
        for (int i=0; i<graph[cur].size(); i++)
        {
            int next = graph[cur][i].first;
            if (!visit[next] && w <= graph[cur][i].second)
            {
                q.push(next);
                visit[next] = true;
            }
        }
    }
 
    return false;
}
 
void binarySearch()
{
    int left = 1;
    int right = 1000000000;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
        memset(visit, false, sizeof(visit));
 
        if (bfs(mid))
        {
            result = max(result, mid);
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> M;
 
    for (int i=0; i<M; i++)
    {
        cin >> A >> B >> C;
        graph[A].push_back({B, C});
        graph[B].push_back({A, C});
    }
 
    cin >> from >> to;
    binarySearch();
 
    cout << result;
 
    return 0;
}