백준 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의 시간소모.

 

소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#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; } Colored by Color Scripter

cs