[C++][백준] 인터넷설치(1800)

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

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

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

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

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

출력
첫째 줄에 원장선생님이 내게 되는 최소의 돈을 출력한다. 만약 1번과 N번 컴퓨터를 잇는 것이 불가능 하다면 -1을 출력한다.

 

풀이

문제가 살짝 장황하게 느껴졌는데, "1 → N번 컴퓨터를 연결하는 경로 중 케이블 K개를 제외한 가장 비싼 케이블 값만 지불한다. 이 때, 지불 비용의 최솟값을 구하라." 라고 문제를 정리할 수 있습니다.

 

문제의 조건을 살펴보면 우리가 구하려는 값은 다음과 같습니다.

1. 어느 시점부터 가능한 값이다.(1500원으로 가능하다면 1600, 1700원으로도 가능합니다.)

2. 최솟값을 구해야한다.

 

1~2를 종합적으로 생각해보면 조건에 부합하는 value(지불 비용)가 많이 있지만 우리가 찾는 값은 최솟값이다. 라는 결론을 낼 수 있습니다. 따라서 지불 비용을 기준으로 이분 탐색을 진행합니다. 

 

지불 비용 M원으로 1 → N번 컴퓨터를 연결할 수 있는지 확인하기 위해서는 아래 조건을 만족해야 합니다.

 

• 경로 중 가장 비싼 비용이 M원 이하여야 합니다.
• M원보다 비싼 경로가 있다면 그 경로는 K개 이하여야 합니다.(K개 까지는 무료)

다익스트라를 통해 해당 조건을 만족하면서 1 → N번 컴퓨터를 연결할 수 있는지 확인합니다.

 

int solution(int maxValue) {
	int l = 0;  
	int r = maxValue; 

	if (dijkstra(maxValue) == false) return -1;

	while (l < r) {
		int mid = (l + r) / 2;
		if (dijkstra(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}

	return l;
}

지불할 수 있는 비용의 범위는 0원 ~ (가장 큰 값을 갖는 비용)입니다.

mid 값 비용으로 1번 → N번 컴퓨터를 연결할 수 있으면 r의 위치를 mid로 옮겨줍니다.

mid 값 비용으로 1번 → N번 컴퓨터를 연결할 수 없으면 l의 위치를 mid + 1로 옮겨줍니다.

지불 비용의 최솟값을 구하는 것이 목표이기 때문에 지불 불가능한 금액은 관심 영역이 아닙니다.

l, r 값이 같아 지는 시점에 지불 가능한 최솟값을 찾을 수 있습니다.

 

 

 

bool dijkstra(int M) {
	int table[MAX];
	for (int i = 0; i < MAX; i++) {
		table[i] = 987654321;
	}
	priority_queue<pair<int, int>> myPQ;

	table[1] = 0;
	myPQ.push(make_pair(0, 1)); // 비용, 컴퓨터 번호

	while (!myPQ.empty()) {
		int current = myPQ.top().second;
		int cost = myPQ.top().first * -1;
		myPQ.pop();

		if (table[current] < cost) continue;

		for (int i = 0; i < myGraph[current].size(); i++) {
			int next = myGraph[current][i];
			int nCost = myCost[current][i];

			if (nCost <= M) nCost = 0;
			else nCost = 1;

			if (table[next] > cost + nCost) {
				table[next] = cost + nCost;
				myPQ.push(make_pair(-table[next], next));
			}
		}
	}

	if (table[N] == 987654321) {
		return false;
	}
	else {
		if (table[N] > K) return false;
		else return true;
	}
}

우선순위 큐를 사용하여 다익스트라를 구현하였습니다.

table[] 배열에는 비용 값을 기록합니다. (1번 컴퓨터는 이미 연결되어있기 때문에 비용은 0원입니다.)

 

• 경로 중 가장 비싼 비용이 M원 이하여야 합니다.
• M원보다 비싼 경로가 있다면 그 경로는 K개 이하여야 합니다.(K개 까지는 무료)

위 조건을 만족하기 위해 경로 중 M원 이하의 cost는 0, M원보다 비싼 cost는 1로 설정하였습니다.

table[N] > K 의 경우 무료로 사용한 케이블의 수가 K보다 크다는 의미이기 때문에 false를 return합니다.(도착 불가)

table[N] <= K 의 경우 무료로 사용한 케이블의 수가 K 이하면서 비용 M으로 1 → N번 컴퓨터를 연결할 수 있다는 의미이기 때문에 true를 return합니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, P, K;

const int MAX = 1010;
vector<int> myGraph[MAX];
vector<int> myCost[MAX];

bool dijkstra(int M) {
	int table[MAX];
	for (int i = 0; i < MAX; i++) {
		table[i] = 987654321;
	}
	priority_queue<pair<int, int>> myPQ;

	table[1] = 0;
	myPQ.push(make_pair(0, 1)); // 비용, 컴퓨터 번호

	while (!myPQ.empty()) {
		int current = myPQ.top().second;
		int cost = myPQ.top().first * -1;
		myPQ.pop();

		if (table[current] < cost) continue;

		for (int i = 0; i < myGraph[current].size(); i++) {
			int next = myGraph[current][i];
			int nCost = myCost[current][i];

			if (nCost <= M) nCost = 0;
			else nCost = 1;

			if (table[next] > cost + nCost) {
				table[next] = cost + nCost;
				myPQ.push(make_pair(-table[next], next));
			}
		}
	}

	if (table[N] == 987654321) {
		return false;
	}
	else {
		if (table[N] > K) return false;
		else return true;
	}
}

int solution(int maxValue) {
	int l = 0;  
	int r = maxValue; 

	if (dijkstra(maxValue) == false) return -1;

	while (l < r) {
		int mid = (l + r) / 2;
		if (dijkstra(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}

	return l;
}

int main() {
	cin >> N >> P >> K; // N : 컴퓨터 수, P : 케이블선 수, K : 공짜 케이블 수

	int max = -1;
	for (int i = 0; i < P; i++) {
		int computer1, computer2;
		int cost;
		cin >> computer1 >> computer2 >> cost;

		myGraph[computer1].push_back(computer2);
		myGraph[computer2].push_back(computer1);

		myCost[computer1].push_back(cost);
		myCost[computer2].push_back(cost);

		if (cost > max) max = cost;
	}

	cout << solution(max);

	return 0;
}