cdjs의 코딩 공부방

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

1. 문제

- 컴퓨터의 개수 $N$, 케이블선의 개수 $P$, 공짜로 제공하는 케이블선의 개수 $K$가 주어진다.

- 다음 $P$개의 줄에, 연결된 컴퓨터 쌍 A, B와 연결 비용 C가 주어진다.

- 초기에는 1번 컴퓨터에만 인터넷이 연결되어 있고, $N$번 컴퓨터에 인터넷을 연결하는 것이 목표이다. (1, $N$을 제외한 다른 컴퓨터는 인터넷에 연결되지 않아도 된다.)

- 연결하는 비용은 연결한 케이블선을 나열했을 때, $K+1$번째로 비용이 높은 케이블선의 비용이다.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

우선, 가장 간단한 $K=0$인 경우부터 생각해 보자.

$K=0$인 경우, 무료로 주는 케이블선이 없으므로 모든 케이블선을 직접 연결해야 한다.

이 경우에는 케이블선을 최적으로 고르는 방법은 비용이 가장 낮은 케이블선부터 하나씩 차례로 연결해 보면서, $1$번 컴퓨터와 $N$번 컴퓨터가 연결될때 까지, 그리디하게 계속 연결해 보는 것이다.

그러나, $K>0$인 경우를 생각해 보자.

가장 간단하게 생각할 수 있는 방법은 $P$개의 간선 중 $K$개를 모두 고른 다음에, 위에서 말했던 해결 방법을 그대로 적용하는 것이다.

실제로 $K=1$인 경우에는 이런 방법이 통할 수 있겠지만, $K < N \leq 1,000$이고, $P \leq 10,000$이므로 $K, P$가 커지면 이 방법은 시간초과가 나게 될 것이다.

$P$개의 케이블선 중 무료로 받을 $K$개를 모두 탐색하며 문제를 푸는 것은 어떻게 해도 불가능하다는 사실을 알았으니, 여기서 몇 가지 고민들을 할 수 있다.

우선, $P$개의 케이블선 중 $K$개를 고르는 것을 그리디하게 구할 수 있는지 고민해 보면, 어떻게 해도 불가능하다는 것을 깨달을 수 있다.

가장 비싼 $K$개의 케이블선을 고르는 경우는 당연히 최선이 아닐 뿐더러, $K$개의 케이블선을 골랐을 때와 고르지 않았을 때 최소 비용의 경로가 아예 달라지기 때문이다. 즉, 무료로 받은 $K$개를 제외한 간선을 연결하기 전에는 $K$개의 무료 간선을 고를 수 없다는 것이다.

여기서 잠깐 종합해 보자.

$K=0$이라고 생각했을 때는 그리디하게 케이블선들을 연결할 수 있었다.

그렇다면 $K>0$인 경우는 어떨까?

이미 그리디하게 연결된 케이블선들 중 가장 높은 비용의 케이블선 $K$개를 무료로 받을 때, 무료로 받은 케이블선 비용 미만의 케이블선과, 지금 무료로 받은 케이블선들만으로 $1$번 컴퓨터와 $N$번 컴퓨터를 연결할 수 있다면 최소 비용은 조금씩 낮아지게 된다.

이 때, 만약 처음에 $X$ 이하의 비용만으로 이미 $1$번 컴퓨터와 $N$번 컴퓨터를 연결할 수 있었다고 한다면, 무료로 받는 케이블선이 아닌 이상 $X+1$ 이상의 비용을 가진 케이블선을 추가로 고를 필요가 전혀 없다.

또한, 비용이 $X$ 이하인 케이블선만 고른다면 고른 케이블선이 $1$번 컴퓨터와 $N$번 컴퓨터를 연결하는지 여부와 관계 없이 어차피 총 비용은 $X$ 이하이다.

따라서, 우리는 이런 풀이를 생각해볼 수 있다.

"비용이 $X$ 이하인 케이블선들을 모두 고른 뒤에, $K$개 이하의 케이블선만으로 $1$번 컴퓨터와 $N$번 컴퓨터까지 연결할 수 있다면, 총 비용은 $X$ 이하일 것이다."

여기까지 왔다면 풀이 방식이 상당히 다양한데, 필자는 다익스트라 기법으로 접근했다.

케이블 쌍 개수가 $10,000$개 이하이므로 사실 케이블선 비용의 종류는 최대 $10,000$개이다.

그래서, $solve(x)$를 "비용이 $x$ 이하인 간선을 제외하고 $K$개 이하의 간선만을 이용하여 $1$번 컴퓨터와 $N$번 컴퓨터를 연결할 수 있는가?" 라는 뜻으로 만들었다.

그리고 나서, $1$번 노드부터 시작해서 비용이 $x$ 이하라면 $cost$값을 그대로 두면서 pq에 집어넣고, $x$ 초과라면 $cost$값을 1 증가시키면서 pq에 집어넣었다.

그렇게 맞았습니다!! 를 받을 수 있었다.

그런데.. 사실 이 풀이는 간단히 생각하면 $O(P^2 log(N))$이라 시간 안에 안될 가능성이 있다. 

물론 저런 시간복잡도가 나오려면 정말 최악의 경우로 나와야 하지만, 가격이 $1,000,000$ 이하이고 케이블선 개수도 $10,000$개 이하이므로 사실 이론적인 최악의 경우로 나오는 것이 불가능하므로 문제가 풀린다.

다만 조금만 더 생각해 보면 더 빠른 풀이를 생각할 수 있는데, 매개변수 탐색(Parametric Search)를 사용하면 더욱 빠르게 문제를 풀 수 있다.

즉, 어차피 비용은 $1,000,000$ 이하이므로 l=$0$, r=$1,000,000$으로 두고 이분 탐색을 진행하며 $solve(mid)$가 $True$값을 내는 최소 $mid$값이 정답이라고 하고 제출하는 것이다.

이러면 시간복잡도는 $O(P log(N) log(1,000,000) )$이 되므로, 무조건 시간 안에 풀린다.

아래 코드는 매개변수 탐색 방법을 적용하여 푼 코드이다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<vector<pair<int, int>>> v;
int n, p, k;

bool solve(int piv) {
    // piv 이하의 간선을 제외한 k개의 간선만 사용해서 1~n링크를 만들 수 있는지 여부 판단
    vector<int> cost(n+1, n);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        int node = pq.top().second;
        int maxx = pq.top().first;
        pq.pop();
        if (cost[node] <= maxx)  continue;
        cost[node] = maxx;

        for (int i=0; i<v[node].size(); i++) {
            if (v[node][i].second <= piv && cost[v[node][i].first] > maxx) {
                pq.push({maxx, v[node][i].first});
            }
            else if (v[node][i].second > piv && cost[v[node][i].first] > maxx + 1) {
                pq.push({maxx+1, v[node][i].first});
            }
        }
    }

    if (cost[n]<=k) return true;
    else    return false;
}

int main() {
    int ans;
    int a, b, c;
    int costs[1000001];
    memset(costs, 0, sizeof(costs));
    cin >> n >> p >> k;
    v = vector<vector<pair<int, int>>>(n+1);

    for (int i=0; i<p; i++) {
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
        costs[c]=1;
    }
    costs[0] = 1;
    ans = -1;
    int l, r, mid;
    l=0;    r=1000001;  mid=(l+r)/2;
    while (l<r) {
        mid = (l+r)/2;
        if (solve(mid)) {
            ans = mid;
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans;
}

5. 여담

사실 풀기 전에 "매개 변수 탐색 각인데?" 했다가 "안해도 풀리겠다" 싶어서 그냥 풀었는데, 풀고 나서 태그에 매개 변수 탐색이 박혀 있길래 매개변수 탐색으로 다시 한번 풀어봤다.

문제 출제 년도가 2008년이다보니까 $P$ 조건을 굉장히 널널하게 준 것 같은데, 아마 최근 대회였으면 $P$ 조건을 10만정도로 주지 않았을까 싶다.