[백준 13905번] 세부 (C++)

문제링크 :https://www.acmicpc.net/problem/13905

13905번: 세부

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M, s, e;
int h1, h2, k;

vector <pii> arr[100001];
bool check[100001];

bool bfs(int m)
{
    queue<int>q;
    memset(check, 0, sizeof(check));
    q.push(s);
    check[s] = true;

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

        if(cur == e) return true;

        for(int i=0; i<arr[cur].size(); i++)
        {
            int n_node = arr[cur][i].first;
            int n_cost = arr[cur][i].second;

            if(!check[n_node] && n_cost >= m) //다음 무게제한이 현재 무게제한보다 같거나 크다면
            {
                check[n_node] = true;
                q.push(n_node);
            }
        }
    }
    return false;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    cin >> s >> e;

    for(int i=0; i<M; i++)
    {
        cin >> h1 >> h2 >> k;
        arr[h1].push_back({h2, k});
        arr[h2].push_back({h1, k});
    }

    int l = 1, h = 1000000, mid, result = 0;

    while(l<=h)
    {
        mid = (l + h)/2;
        if(bfs(mid))
        {
            result = mid;  //도달한 경우
            l = mid + 1;
        }
        else
        {
            h = mid - 1;
        }
    }

    cout << result;

    return 0;
}

일일히 전부 확인하여 완전탐색으로 풀면 시간초과가 나기에 이분탐색을 활용했다.

지금의 무게를 기준으로 다음 무게제한이 현재 무게제한보다 같거나 크다면 통과시켰다.

무게 값의 범위가 1 ~ 100만이므로 low를 1, high를 100만으로 초기화했다.

 

현재 무게(mid 값)가 마지막 종착지까지 갔다면 무사히 통과한 것이므로 result에 결과값을 담고, 더 큰 무게로 통과가 가능한지 확인을 위해 low의 값에 mid + 1을 대입한다.

반대로 현재 무게가 마지막 종착지까지 못갔다면 무게가 너무 무거운 것이므로 high의 값에 mid - 1을 해줌으로써 무게를 줄여준다.

그리고 탐색을 할 때마다 방문을 체크하는 bool 배열을 다시 fasle로 초기화시켜주어 정상적인 탐색이 가능하도록 해야한다.