백준 1939 중량제한 :: 들짐승

<링크>

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

<소스코드>

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
queue<int> q;
vector<pair<int, int>> adj[10001];
int s, d;
int bfs(int);
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    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 });
    }
    scanf("%d%d", &s, &d);
    int ans = 0;
    int l = 1, r = 1000000000;
    int m;
    while (l <= r)
    {
        m = (l + r) / 2;
        int to = bfs(m);
        if (to) {
            if (ans < m)
                ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%d", ans);
}
int bfs(int weight)
{
    int isVisited[10001] = { 0, };
    q = queue<int>();
    isVisited[s] = 1;
    q.push(s);
    
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        if (cur == d)
            return 1;
        int s = adj[cur].size();
        for (int i = 0; i < s; ++i)
        {
            int to = adj[cur][i].first;
            int cost = adj[cur][i].second;
            if (!isVisited[to] && cost >= weight)
            {
                isVisited[to] = 1;
                q.push(to);
            }
        }
    }
    return 0;
}
    
 

<풀이>

이분탐색 + BFS문제이다.

A도시에서 B도시까지 넘겨줄 수 있는 최대중량을 이분탐색으로 찍는다.

이분탐색은 답을 찍어볼 때 굉장히 유용하다는 것을 다시 한번 느꼈다.

2018/07/22 - [알고리즘 풀이/이분탐색] - 백준 3079 입국심사 :: 들짐승

찍는 값의 범위는 1~1000000000 이다.

찍은 값으로 BFS를 돌린다. 

현재 노드와 인접해있고, 방문하지 않았으며, 넘어가는 다리의 용량이 내가 찍은 값보다 같거나 크면 넘어갈 수 있으므로 큐에 넣어준다.

도착지가 발견되면 더이상 가지를 뻗을 필요가 없으므로 리턴한다.

이 때, 넘어가는 다리의 용량이 내가 찍은 값보다 같거나 크면 이라는 조건 때문에 도착지를 발견못하고 큐가 비어버렸을 때는

0을 리턴해주고,

도착지를 찾은 경우 1을 리턴한다.

● 0이 리턴된 경우 : 찍어봤던 중량을 더 줄여봐야하기 때문에 right=mid-1

● 1이 리턴된 경우 : 찍어봤던 중량이 가능하다는 뜻이므로 최적의 값을 찾기 위해 더 큰 중량으로 실행해본다. left=mid+1

이 때, 정답을 갱신한다.

<시간복잡도>

이분탐색시간 :

 

BFS시간 : 인접리스트로 구현했기 때문에

따라서 최대 3300,000 이 걸리기 때문에 1초 안에 가능하다.