[ 백준 1939 ] 중량제한 (파라메트릭 서치)

파라메트릭 서치란?

최적화 문제를 결정 문제(decision problem)으로 바꾼 뒤, 이것을 이분법을 이용해 해결하는 방법이다.

문제

백준 1939번

풀이

중량제한 문제를 파라메트릭 서치에 적용시켜보면, 다음과 같이 설명할 수 있다.

최적화 문제

다리에 대한 정보가 주어졌을 때, 중량의 최댓값을 반환

while (left <= right) {
    memset(visited, false, sizeof(visited));
    int mid = (left + right) / 2;
    if (bfs(mid)) {
    	left = mid + 1;
        ans = mid;
    }
    else right = mid - 1;
}

결정 문제

다리에 대한 정보(v)와 중량제한의 값(mid)가 주어졌을 때, 공장이 있는 두 섬을 중량제한 값 이상으로 오갈 수 있는 방법이 있는가? (공장이 있는 두 섬을 연결하는 경로 중 다리의 중량제한 값들이 주어진 중량제한의 값 이상인가? 즉, 모든 다리의 중량제한의 값이 mid 이상인 경로가 있는가?)

bool bfs(int mid) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int from = q.front();
        q.pop();
        if (from == fin) return true;
        for (int i = 0; i < v[from].size(); i++) {
            int next = v[from][i].first;
            int nextC = v[from][i].second;
            if (visited[next]) continue;
            if (mid <= nextC) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return false;
}

파라메트릭 서치를 하기 위해서는 결정 문제에서 "모든 경로의 중량제한의 값이 mid인 경로가 있는가?"가 아니라 "모든 경로의 중량제한의 값이 mid 이상인 경로가 있는가?"라는 질문에 답해야 한다. 달리 말해, 결정문제는 "답 x가 존재하는가?"가 아니라 "x 또는 그보다 좋은 답이 있는가?"라는 질문에 대답해야 한다. 그렇게 해야 답의 후보가 되는 구간이 연속적으로 존재해서, 최적화 문제에서 답이 존재하는 범위를 절반으로 줄여나가며 최종적으로는 답이 있는 위치를 맞출 수 있기 때문이다.

중량제한 문제에서는 초기에는 left = 0, right = 3(중량제한 값 중 최대값)이고, 우리가 원하는 답은 [0,3] 사이에 있을 것이다.

• left와 right의 절반인 mid = 1, 답의 후보가 [1,3] 사이에 존재하는지 BFS로 검사한다.

• 중량제한 값이 mid 이상인 경로가 있었으므로 구간을 절반으로 나눠 [2,3]에 존재하는지 다시 검사한다.

• 중량제한 값이 mid 이상인 경로가 있었으므로 구간을 절반으로 나눠 [3,3]에 존재하는지 다시 검사한다.

• 답이 존재하는 위치를 완전히 줄였고, 답이 3이었음을 알 수 있다.

정리하자면, 파라메트릭 서치는 다음과 같이 풀 수 있다.

결정 문제를 정의했을 때, 정답이 될 수 있는 값들이 연속적인 경우
최솟값을 구하는 경우: 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족
최댓값을 구하는 경우: 최댓값이 x라면, x이하의 값에 대해서는 모두 조건을 만족

코드

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
 
int N, M, start, fin;
vector<pair<int, int>> v[100000];
bool visited[100000];
 
bool bfs(int mid) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int from = q.front();
        q.pop();
        if (from == fin) return true;
        for (int i = 0; i < v[from].size(); i++) {
            int next = v[from][i].first;
            int nextC = v[from][i].second;
            if (visited[next]) continue;
            if (mid <= nextC) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    int left = 0, right = 0;
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        v[A].push_back(make_pair(B, C));
        v[B].push_back(make_pair(A, C));
        if (right < C) right = C;
    }
    cin >> start >> fin;
 
    int ans = 0;
    while (left <= right) {
        memset(visited, false, sizeof(visited));
        int mid = (left + right) / 2;
        if (bfs(mid)) {
            left = mid + 1;
            ans = mid;
        }
        else right = mid - 1;
    }
    cout << ans;
    return 0;
}

출처

종만북 12단원
주니어 개발자의 대나무숲