Baekjoon 1800번 인터넷 설치

문제

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

걸린 시간

01 : 25 : 03 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, p, k, v, u, w;
vector<pair<int, int>> adj[1001];

bool decision(int x){
    vector<int> dist(1001, INF);
    dist[1] = 0;
    priority_queue<pair<int, int>> pq; // cost, vertex
    pq.push(make_pair(0, 1));
    while(!pq.empty()){
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if(dist[here] < cost) continue;
        for(int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextDist = cost + (adj[here][i].second > x);
            if(dist[there] > nextDist){
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    return dist[n] <= k;
}

int optimize(){
    int ans = -1;
    int left = 0;
    int right = 1e7;
    while(left <= right){
        int mid = (left+right)/2;
        if(decision(mid)){
            right = mid-1;
            ans = mid;
        }
        else{
            left = mid+1;
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> p >> k;
    for(int i = 0; i < p; i++){
        cin >> v >> u >> w;    
        adj[v].push_back(make_pair(u, w));
        adj[u].push_back(make_pair(v, w));
    }
    cout << optimize();
    return 0;
}

1번부터 N번까지 컴퓨터가 있다. 1번 컴퓨터만 인터넷에 연결되어 있는 상태에서 N번째 컴퓨터가 인터넷에 연결되도록 케이블선을 설치하려고 한다. 케이블선의 비용은 각각 다르다.

라는 정보로부터 가중치가 있는 그래프의 형태를 띄는 것을 알 수 있다.

1번과 N번 컴퓨터를 연결시키기 위한 최소 케이블 비용을 구하라는 문제라면 간단히 다익스트라 알고리즘을 사용하면 되지만, 문제는 1번과 N번 컴퓨터를 잇는 경로에서 k개의 엣지를 제외한 나머지 엣지들 중 가장 비싼 가격을 최소화 하려고 한다. 즉, 1번과 N번을 잇는 경로의 구성이 중요하다.

여기까지 문제를 파악했지만 백트래킹이 내가 떠올릴 수 있는 방법의 한계였다.

해설을 보니 최적화 문제를 결정 문제로 바꾸어 푸는 파라메트릭 서치 문제였다. 정답이 될 수 있는 값의 범위를 1부터 1e7으로 설정하고 이분 탐색을 진행하며 현재 값(x)이 정답이 될 수 있는지를 판단한다. 정답이 되려면 x 보다 크기가 큰 엣지의 가중치들의 개수가 k개 이하여야 한다. x 보다 크기가 큰 엣지의 가중치가 가장 적은 경로를 찾아야 하므로 x 보다 크기가 큰 엣지는 1, 작거나 같은 엣지는 0 으로 바꾸어 다익스트라 알고리즘을 수행한 후 k보다 작거나 같은지를 참, 거짓으로 반환하면 된다.