[백준] 1939번 중량제한

1939 중량제한

문제

---

N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

---

첫째 줄에 답을 출력한다.

---

풀이) 

bfs와 binary search를 이용해서 푼 문제이다.

다리사이의 연결 여부는 인접리스트로 표현했다.

vector pair<int,int> adj[100001] -> adj[a][b] = a섬에서 b섬까지의 다리의 중량제한

과정을 살펴보자면.

1. binary serach를 이용해 다리가 가져야 할 최소 중량 mid를 정한다.

2. bfs를 통해 섬과 섬 사이의 연결 여부를 확인하고, 중량이 mid를 넘지 않는 다리이면 건너지 않는다.

3. 목적지 섬까지 갔다면, 최소 중량을 늘려도 된다는 얘기니깐 늘린다.

   가지 못했다면, 최소 중량이 컸다는 얘기이므로 중량을 줄인다.

1,2,3을 반복하여, 중량의 최대값을 구한다.

그림으로 보자면

아래의 예시같은 경우 답이 9이다. (1번 섬에서 6번 섬까지 간다고 할때)

내가 푼식으로 경로를 표시해보았다.

코드)

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
 
int n, m;
vector<pair<int,int>> adj[100001];
int island1, island2;
int mid;
bool visited[100001];
 
void bfs() {
    queue <int> qu;
    qu.push(island1);
    visited[island1] = true;
 
    while (!qu.empty())
    {
        int here = qu.front();
        qu.pop();
        for (int i = 0; i < adj[here].size(); i++) {
            //이미 방문했던 곳이거나, 다리의 중량이 지정한 중량을 (못)넘으면 pass
            if (visited[adj[here][i].first] || adj[here][i].second < mid) continue;
            visited[adj[here][i].first] = true;
            qu.push(adj[here][i].first);
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
 
    int start = 1;
    int end =0;
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
        end = max(end, c);
    }
    end++;
    scanf("%d %d", &island1, &island2);
    int result = 0;
    while (end > start)
    {
        mid = (start + end) / 2;
        bfs();
        //만약 지정한 무게대로 목적지로 갈 수 있다면
        if (visited[island2]) {
            result = max(result, mid);
            start = mid + 1; //무게 늘려보기
        }
        else {
            end = mid; // 무게 줄이기
        }
        fill(visited, visited + n + 1, false);
 
    }
    printf("%d", result);
    return 0;
}