[백준 1939] 중량제한

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

처음엔 크루스칼 알고리즘밖에 떠오르지 않았다. 가중치의 최댓값을 작고 점점 작게 탐색한다면... 쉽게 할 수 있을 것 같았다.
그러나! 나는 이분 탐색을 공부 중이기때문에, 이분 탐색으로 어케할지 이리저리 고민해봤다...

파라메트릭 서치

문제를 풀고 여러 블로그들을 돌아보니, 이런 종류의 문제에서 사용된 이분 탐색기법을 파라메트릭 서치라고 불렀다.

파라메트릭 서치란 어떠한 정렬된 리스트에서 원하는 값을 찾는 이분 탐색과 달리 조건에 부합하는 값을 찾는 것이다.

파라메트릭 서치를 사용하기 위해선 세가지 조건이 있다.

• 조건을 만족하는 최대,최소를 구하는 문제여야 한다.
• 최댓값이 조건을 만족한다면, 최댓값보다 작은 값도 만족해야 한다.
• 답의 범위가 정수이거나 허용 오차 범위가 있어야 한다.

시간 복잡도

• 이진 탐색 $O(log(maxWeight))$ * bfs탐색(정점n + 간선 m) $O(n+m)$
  => $O(nlogn)$

문제 풀이

1. 입력을 받으며 최대 가중치를 구함
2. 최대 가중치와 최소 가중치의 중간 값을 구함
3. 시작지점부터 bfs를 하며 간선을 이동
   • 만약 간선의 가중치가 2번에서 구한 값보다 크면 계속 움직이고 아니면 break
4. 도착지점 까지 움직였으면 최소 가중치를 2번 값 + 1
5. 아니라면 최대 가중치를 2번 값 - 1

구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int, int>>> edge(n + 1); // [start] first:end second:w
    int max_weight = 0;
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a].push_back({b, c});
        edge[b].push_back({a, c}); 
        max_weight = max(max_weight, c);
    }
    
    int s, e;
    cin >> s >> e;

    int min_weight = 1;
    
    while (min_weight <= max_weight) {
        int current_weight = (min_weight + max_weight) / 2;
        
        vector<bool> visit(n + 1, false);
        visit[s] = true;

        queue<int> q;
        q.push(s);

        bool can_reach = false;
        
        while (!q.empty()) {
            int start = q.front();
            q.pop();

            if (start == e) {
                can_reach = true;
                break;
            }

            for (auto& edg : edge[start]) {
                int next = edg.first;
                int w = edg.second;

                if (!visit[next] && w >= current_weight) {
                    visit[next] = true;
                    q.push(next);
                }
            }
        }

        if (can_reach) min_weight = current_weight + 1;
        else max_weight = current_weight - 1;
    }

    cout << max_weight;

    return 0;
}

참고
https://ialy1595.github.io/post/parametric-search/