백준 1939번 중량제한

문제링크

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

 

사용 알고리즘

  º  BFS, 이분탐색

 

시간복잡도

  º  $\mathcal{O}(NlogC)$  N(2≤N≤10,000), M(1≤M≤100,000), C(1≤C≤1,000,000,000)

 

풀이

 

섬들 간 사이를 잇는 다리의 정보와 다리의 중량 제한들이 입력으로 주어질 때, 시작섬과 도착섬을 오갈 수 있는 물품들의 최대 중량값을 구하는 문제입니다. 중량값을 기준으로 탐색을 진행하여 그 중량으로 이동이 가능한지 검사를 해주면 해결할 수 있는 문제였습니다.

 

1.  이분탐색을 사용하여 최소무게 1부터 입력 받은 최대무게 사이를 이분탐색하여 현재 물품들의 중량(cost)이 시작섬에서 도착섬까지 이동가는한지 검사합니다. 최대 무게는 10억이므로  $\mathcal{O}(log10^10)$ = 10의 시간소모.

 

2. BFS또는 DFS로 그래프를 설정한 무게(cost)로 탐색해줍니다. $\mathcal{O}(10000+100000)$ = 110000의 시간소모.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, max_cost, st, ed;
vector <pair<int, int>> v[10001];
bool bfs(int cost)
{
    vector <bool> check(n + 1); // 방문을 표시할 bool 배열
    check[st] = true;
    queue <int> q;
    q.push(st);
    int cur, next, next_cost;
    while (!q.empty())
    {
        cur = q.front();
        q.pop();
        if (cur == ed) // 도착섬에 도착
            return true;
        for (int i = 0; i < v[cur].size(); i++)
        {
            next = v[cur][i].first;
            next_cost = v[cur][i].second;
            if (check[next] == false && cost <= next_cost) // 방문한적없고 물품들의 무게가 다음섬의 제한보다 작으면 이동가능
            {
                check[next] = true;
                q.push({ next });
            }
        }
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
        if (c > max_cost)
            max_cost = c;
    }
    cin >> st >> ed;
    int ans = 0, mid, left = 1, right = max_cost; // 무게의 최소값은 1, 최대값은 제한의 최대 무게
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (bfs(mid)) // 현재 중량의 물품들로 공장간의 이동을 할 수 있는지 bfs탐색으로 검사
        {
            left = mid + 1;
            if (mid > ans)
                ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}