전화선 최소 비용 계산

문제 개요 농부 존은 자신의 농장에 전화선을 설치해야 한다. 그러나 통신사의 협조가 부족하여, 일부 전화선은 비용을 지불해야 한다. 전체적으로는 N (1 ≤ N ≤ 1,000)개의 전화 기둥이 있으며, 각각 1부터 N까지 번호가 매겨져 있다. 현재는 아무 기둥도 연결되어 있지 않다. 총 P (1 ≤ P ≤ 10,000)개의 기둥 쌍 사이에 전화선을 설치할 수 있으며, 나머지는 거리가 너무 멀어 연결 불가능하다.

각 전화선은 두 기둥 Ai, Bi를 연결하며 길이는 Li (1 ≤ Li ≤ 1,000,000) 단위이다. 입력 데이터에서는 같은 기둥 쌍이 중복으로 주어지지 않는다. 기둥 1은 이미 전국 전화망과 연결되어 있고, 기둥 N은 농장 위치이다. 따라서 목표는 기둥 1과 N을 연결하는 경로를 찾는 것이다. 다른 기둥들은 선택적 사용이 가능하다.

통신사는 농부 존에게 무료로 K (0 ≤ K < N)개의 전화선을 제공한다. 이보다 더 많은 선은 유료이며, 요금은 사용된 전화선 중 가장 긴 것의 길이와 동일하다. 만약 필요한 선이 K개 이하라면 비용은 0이다.

최소 비용을 구하라.

입력 형식 첫째 줄에 세 정수 N, P, K가 주어진다. 이후 P개의 줄에 각각 ai, bi, li가 주어진다.

출력 형식 최소 비용을 출력한다. 불가능한 경우 -1을 출력한다.

예제 입력

예제 출력

접근 방식 이 문제는 최소화되는 최대값을 찾는 문제로, 이는 이분 탐색을 활용할 수 있다.

정답 후보 값 x가 유효하다는 것은, 기둥 1에서 N으로 가는 경로 상에서 길이가 x보다 큰 전화선의 개수가 K 이하라는 의미이다. 즉, 이러한 길이를 초과하는 선은 최대 K개까지만 허용된다.

따라서 우리는 가능한 최소의 x를 이분 탐색으로 찾는다. 이때 check(x) 함수는 다음과 같이 정의된다:

모든 간선의 길이가 x 이상이면 1, 그렇지 않으면 0으로 가중치를 부여한다.
이 가중치 기준으로 기둥 1에서 N까지의 최단 경로를 계산한다.
이 경로의 총 가중치가 K 이하이면 x는 유효하다.

이러한 경로 탐색은 간선 가중치가 0 또는 1뿐이므로, 0-1 BFS (덱을 이용한 BFS)를 통해 효율적으로 수행할 수 있다.

이분 탐색 범위는 [0, 1e6 + 1]이다.

왼쪽 끝인 0은 경로에 필요한 선이 K 이하일 때 비용이 0이라는 의미.
오른쪽 끝인 1,000,001은 도달 불가능한 경우를 위한 예외 처리용.

최종적으로, 이분 탐색을 통해 만족하는 최소 x 값을 찾고, 그 값이 1,000,001이라면 도달 불가능하므로 -1을 반환한다.

코드 구현

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1005;
const int MAX_M = 20005;

int n, p, k;
int head[MAX_N], edge[MAX_M], weight[MAX_M], next_edge[MAX_M], idx;
deque<int> dq;
int dist[MAX_N];
bool visited[MAX_N];

void add_edge(int u, int v, int w) {
    edge[idx] = v;
    weight[idx] = w;
    next_edge[idx] = head[u];
    head[u] = idx++;
}

bool check(int threshold) {
    memset(dist, 0x3f, sizeof(dist));
    memset(visited, 0, sizeof(visited));
    dist[1] = 0;
    dq.push_back(1);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        if (visited[u]) continue;
        visited[u] = true;

        for (int i = head[u]; i != -1; i = next_edge[i]) {
            int v = edge[i];
            int cost = (weight[i] > threshold) ? 1 : 0;
            int new_dist = dist[u] + cost;

            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                if (cost == 0) {
                    dq.push_front(v);
                } else {
                    dq.push_back(v);
                }
            }
        }
    }

    return dist[n] <= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p >> k;

    // 초기화
    memset(head, -1, sizeof(head));
    idx = 0;

    for (int i = 0; i < p; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        add_edge(a, b, l);
        add_edge(b, a, l);
    }

    int left = 0, right = 1000001;
    int answer = right;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    if (answer == 1000001) {
        cout << -1 << '\n';
    } else {
        cout << answer << '\n';
    }

    return 0;
}

태그: 이분탐색 0-1 BFS 그래프 탐색 최소비용 경로 최대값 최소화

5월 22일 11:20에 게시됨

괴물 클럽

전화선 최소 비용 계산

인기 태그