백준 1800 - 인터넷 설치

 

 

문제 설명

오늘 팀전을 다들 열심히 하시는 것을 보고 원장선생님은 세미나 실에 인터넷을 설치해 주기로 마음을 먹으셨다. 하지만 비 협조적인 코레스코 콘도는 원장님께서 학생들에게 인터넷 선을 연결하는 것에 대해서 일부에 대해 돈을 요구하였다.

각각의 학생들의 번호가 1부터 N까지 붙여져 있다고 하면 아무나 서로 인터넷 선이 연결되어 있지 않다. P(P<=10,000)개의 쌍만이 서로 이어 질수 있으며 서로 선을 연결하는데 가격이 다르다.

1번은 다행히 인터넷 서버와 바로 연결되어 있어 인터넷이 가능하다. 우리의 목표는 N번 컴퓨터가 인터넷에 연결하는 것이다. 나머지 컴퓨터는 연결 되어 있거나 연결 안되어 있어도 무방하다.

하지만 코레스코에서는 K개의 인터넷 선에 대해서는 공짜로 연결해주기로 하였다. 그리고 나머지 인터넷 선에 대해서는 남은 것 중 제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다. 이때 원장선생님이 내게 되는 최소의 값을 구하여라.

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

---

 

 

 

 

 

 

제한 사항

첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차례로 들어온다. 가격은 1 이상 1,000,000 이하다.

---

 

 

 

 

 

 

풀이

문제를 요약하면, 1부터 N까지가는 비용은 간선의 가중치 중 가장 큰 가중치가 된다.

이때, K개의 간선의 가중치를 제외할 수 있다.

1부터 N까지의 최소 비용을 구해야 한다.

 

처음에는 DFS를 통해 가중치를 모아 N에 도달하면 K개를 제외한 뒤, 가장 큰 가중치를 골랐다.

근데 시간초과로 실패했다.

 

시간을 줄이기 위해 여러 가지 시도를 해봤다.

근데 논리적으로 맞지 않았다.

가장 먼저 도착하는 경로가 해당 문제에서 정답이 되지 않으며, 가중치끼리의 크고 작음은 N까지 도달해야 비교할 수 있다.

따라서, 최댓값을 유지하며 진행하는 것도 불가능하다.

 

정답은 접근법을 아예 바꿔야 했다.

해당 문제는 parametric search를 이용해 결정문제로 변경해야 한다.

특정 기준 x로 1부터 N까지 경로를 연결할 수 있는지 결정하면 된다.

즉, 문제를 다음과 같이 나눌 수 있다.

• 1부터 1,000,000까지 값을 이진 탐색을 통해 최적해를 고른다.
• 정해진 x값으로 경로를 연결할 수 있는지 판단한다.

x값으로 경로를 연결할 수 있는지 판단하는 작업은 다익스트라를 통해 구현할 수 있다.

1~N까지의 가중치중 K를 넘는 가중치의 개수를 dist배열에 저장한다.

일단 다음 노드까지의 비용이 x를 넘는다면 제외한다고 가정하는 것이다.

마지막에 dist[N]이 K보다 크다면 K개 이상의 간선이 제외된 것이다.

 

즉, 임의의 값 x는 x를 넘는 간선을 K개 이하로 제외하며 N에 도달할 수 있는 수 중 가장 작은 수가 되는 것이다.

N까지의 도달이 실패하면 x를 늘리고 성공한다면 x를 줄이면 된다.

 

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>

using namespace std;

bool Dijk(vector<vector<pair<int, int>>>& Cable, int x, int N, int K) {
	priority_queue<pair<int, int>> pq;
	vector<int> dist(N + 1, INT_MAX);
	pq.push({ 0, 1 });

	while (!pq.empty()) {
		auto [currentCnt, current] = pq.top();
		currentCnt *= -1;
		pq.pop();

		if (dist[current] < currentCnt) continue;

		for (int i = 0; i < Cable[current].size(); i++) {
			auto [next, nextCost] = Cable[current][i];

			int w = currentCnt + (nextCost > x);
			if (dist[next] > w) {
				dist[next] = w;
				pq.push({ -w, next });
			}
		}
	}

	return dist[N] <= K;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, P, K;
    cin >> N >> P >> K;

    vector<vector<pair<int, int>>> Cable(N+1);

    for (int i = 0; i < P; i++)
    {
        int a, b, cost;
        cin >> a >> b >> cost;

        Cable[a].push_back({ b, cost });
        Cable[b].push_back({ a, cost });
    }

	int l = 0, r = 1'000'000, ans = -1;

	while (l <= r) {
		int mid = (l + r) / 2;

		if (Dijk(Cable, mid, N, K)) {
			r = mid - 1;
			ans = mid;
		}
		else {
			l = mid + 1;
		}
	}

	cout << ans;

    return 0;
}

---