[BOJ] 1800 : 인터넷 설치

문제 링크

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

1800번: 인터넷 설치

1번과 N번 컴퓨터를 연결시키기 위해 필요한 비용중 최대값의 최소가 되도록하는 문제.

풀이

일단 1번과 N번 컴퓨터를 최대 효율로 연결시켜야 하므로 다익스트라 알고리즘을 사용해야하는 것을 알 수 있다. 그런데 기존 다익스트라는 비용이 계속해서 누적된다. 그리고 그 누적 비용이 가작 적게 들도록 N에 도달하는 것이 보통인데, 여기서는 비용들 중 가장 비싼 것에 대해서만 비용을 지불한다. 즉 1 -> N을 연결시키는데 각 4, 5, 6 의 비용이 들었따고 하면 제일 비싼 6에 대해서만 값을 지불한다. 그리고 K개에 대해서는 비용을 받지 않기때문에 K개는 비용 상관없이 연결 가능하다.

일단 먼저 떠올릴 수 있는 다익스트라 정렬 조건은

1. 가격이 싼 것 순으로 연결시킨다.

2. 연결하는 선의 수가 적도록 연결시킨다.

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

하지만 두 가지 경우 모두 예제 1에서 원하는 값을 출력하지 못한다.

1. 가격이 싼 순으로 인터넷을 연결한다.

1 -> 3 -> 4-> 5 로 연결하게 되고 이때 비용이 각각 4, 7, 6 인데 1개는 공짜로 할 수 있으니까 6의 비용을 지불하게 된다. 하지만 1 -> 3 -> 2 -> 5 로 연결하면 비용이 4, 3, 9 인데 9원 짜리는 공짜로 하면 4의 비용을 지불하게 되므로 무조건 싼 순으로 연결하는 것은 해결책이 될 수 없다.

2. 연결하는 선의 수가 최소가 되도록 연결한다.

1 -> 2-> 5 로 연결하면 2번만에 N에 도달한다. 이때 비용은 5, 9 가 발생하고 9원짜리를 공짜로 하면 5원을 지불하게 된다. 이 역시 4원보다 비용이 많이드니까 정답이 아니다.

다익스트라 알고리즘 만으로 해결할 수 없다는 것을 알았다. 이분탐색을 같이 써서 풀어야한다. 지불하는 비용을 mid값으로 설정해준다. 미리 정한 비용(mid)보다 비싼 선을 K개 이하로 연결하게 되면 그때 mid 값은 유효한 값이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 1000 + 5;
vector<pair<int, int>> Edge[MAX_N];
vector<int> dist(MAX_N, INF);
int N, K, P;
 
bool dijkstra(int st, int boundary) {
    Priority_queue pq;
    pq.push({ 0 ,{st, 0} });
    while (!pq.empty()) {
        int now = pq.top().second.first;
        int over = pq.top().first;
        int cost = pq.top().second.second;
        pq.pop();
        if (cost > boundary)
            over++;
        if (over > K)
            continue;
        if (dist[now] <= over)
            continue;
        dist[now] = over;
        if (now == N)
            return true;
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].first;
            int acost = Edge[now][i].second;
            if (dist[next] <= over)
                continue;
            pq.push({ over,{next, acost} });
        }
    }
    return false;
}
int main(void)
{
    int L = 0; int R = -1;
    cin >> N >> P >> K;
    for (int i = 0; i < P; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        R = max(R, w);
        Edge[a].push_back({ b,w });
        Edge[b].push_back({ a,w });
    }
 
    int ans = INF;
    while (L <= R) {
        fill(dist.begin(), dist.end(), INF);
        int mid = (L + R) / 2;
        if (dijkstra(1, mid)) {
            R = mid - 1;
            ans = min(ans, mid);
        }
        else L = mid + 1;
    }
    if (ans == INF)
        cout << "-1\n";
    else cout << ans << "\n";
    return 0;
}

아무리 많은 선을 연결하더라도 미리 정해둔 값 mid 보다 값이 싸다면 몇 개를 연결하든 상관이 없다. 그래서 우선순위 큐 정렬 기준을 mid 보다 비싼 선을 연결한 수가 적은 것을 기준으로 해줬다.