[boj] 백준 1939 중량제한 (c++) - 다익스트라

[문제]

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

1939번: 중량제한

 

[풀이]

다익스트라 최단 경로를 구하는 방식을 응용해서 풀 수 있었다.

인접 정점에 대한 weight[](원래의 dist[] 배열 역할) 갱신 시, 현재 방문 정점에서 옮길 수 있는 최대 중량보다 더 작은 값이 실제 옮길 수 있는 중량이 됨에 유의해야 한다.

 

근데 이후에 찾아보니 이분탐색+bfs로 풀이한 코드가 대부분이었다.. 다양한 방식으로 풀 수 있는 문제인 듯 하다!

이 경우 left=0, right=MAX로 저장 후 mid 값에 대해 그래프 탐색이 가능한지 bfs를 돌린 후, 가능하다면 left 값을 mid+1로, 불가능하다면 right 값을 mid-1로 바꾼 후 반복하는 방식이다.   

 

[코드]

 

1. 다익스트라

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define INF 987654321

using namespace std;

int n, m;
int u, v;
int weight[10001];
vector<pair<int, int>> node[10001];

void dijkstra(int s){
    weight[s] = 1000000001;
    priority_queue<pair<int, int>> q;
    q.push({1000000001, s}); //cost, index

    while(!q.empty()){
        int c = q.top().first;
        int curr = q.top().second;
        q.pop();

        if(weight[curr] > c) continue;

        for(int i=0; i<node[curr].size(); i++){
            int next = node[curr][i].first;
            int cost = min(node[curr][i].second, c);
            if(weight[next] < cost) {
                weight[next] = cost;
                q.push({cost, next});
            }
        }
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        node[a].push_back({b, c});
        node[b].push_back({a, c});
    }
    cin >> u >> v; //공장이 있는 섬의 번호

    fill(weight, weight+10001, -1);
    //u->v 한번에 이동해서 옮길 수 있는 물품들의 중량의 최댓값
    dijkstra(u);
    cout << weight[v];
}

 

2. 이분탐색 + bfs

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define INF 987654321

using namespace std;

int n, m;
int u, v;
bool visited[10001];
vector<pair<int, int>> node[10001];

bool bfs(int mid){
    visited[u] = true;
    queue<int> q;
    q.push(u);

    while(!q.empty()){
        int s = q.front();
        q.pop();

        if(s==v) return true;

        for(int i=0; i<node[s].size(); i++){
            int next = node[s][i].first;
            int weight = node[s][i].second;

            if(!visited[next] && weight>=mid){
                visited[next] = true;
                q.push(next);
            }
        }
    }

    return false;
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        node[a].push_back({b, c});
        node[b].push_back({a, c});
    }
    cin >> u >> v; //공장이 있는 섬의 번호

    int low = 0;
    int high = 1000000001;
    int mid, ans;
    while(low<=high){
        memset(visited, false, sizeof(visited));

        mid = (low+high)/2;
        if(bfs(mid)){
            ans = mid;
            low = mid+1;
        }
        else{
            high = mid-1;
        }
    }

    cout << ans << "\n";
}