[C++][백준] 골목 대장 호석 - 효율성 2(20183)

문제 설명

소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다.

당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다. 하지만 이왕 지나갈 거면, 최소한의 수치심을 받고 싶다. 당신이 받는 수치심은 경로 상에서 가장 많이 낸 돈에 비례하기 때문에, 결국 갈 수 있는 다양한 방법들 중에서 최소한의 수치심을 받으려고 한다. 즉, 한 골목에서 내야 하는 최대 요금을 최소화하는 것이다.

 

당신은 앞선 예제를 통해서, 수치심을 줄이고 싶을 수록 같거나 더 많은 돈이 필요하고, 수치심을 더 받는 것을 감수하면 같거나 더 적은 돈이 필요하게 된다는 것을 알게 되었다. 마을의 지도와 골목마다 존재하는 호석이가 수금하는 금액을 안다면, 당신이 한 골목에서 내야하는 최대 요금의 최솟값을 계산하자. 만약 지금 가진 돈으로는 절대로 목표 지점을 갈 수 없다면 -1 을 출력하라.

 

입력

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 수금액이 공백으로 구분되어 주어진다. 같은 교차로를 잇는 골목은 최대 한 번만 주어지며, 골목은 양방향이다.

 

출력

호석이가 지키고 있는 골목들을 통해서 시작 교차로에서 도착 교차로까지 C 원 이하로 가는 경로들 중에, 지나는 골목의 요금의 최댓값의 최솟값을 출력하라. 만약 갈 수 없다면 -1을 출력한다.

 

풀이

시작 교차로에서 도착 교차로까지 C 원 이하로 가는 경로들 중에, 지나는 골목의 요금의 최댓값의 최솟값을 출력하는 문제입니다.

 

10원을 들고 ① → ③으로 이동해야 할 때 두가지 경로가 존재합니다.

 

① → ② →③

total 비용 : 10

경로 중 최대 비용 : 5

 

① → ④ → ⑤ →③ 

total 비용 : 8

경로 중 최대 비용 : 6

 

이때 두 번째 방법이 total 비용이 더 낮지만 첫 번째 방법이 [경로 중 최대 비용] 이 더 낮기 때문에 첫 번째 방법을 선택합니다.

 

문제를 다시 정리해보면 A → B로 지나는 모든 경로 중(가진 돈으로 갈 수 있어야 함) 지나는 골목 요금의 최댓값의 최솟값을 구하는 문제입니다. 해당 문제는 이분탐색으로 풀이하였습니다.(최솟값이나 최댓값을 구하는 문제는 이분탐색을 고려할 수 있습니다.

 

 

 

long long solution() {
	long long l = 1, r = maxCost + 1;
	while (l < r) {
		long long mid = (l + r) / 2;

		checkInit();
		if (getRoute(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	if (r > maxCost) return -1;
	return r;
}

즉 이분탐색을 통해 우리가 구해야 하는 답은 TARGET 입니다.

위 예시를 적용해보면 TARGET은 5이며 이 값은 지나는 경로 중 지불 수금액의 최댓값 중 최솟값입니다.

 

[경로 중 지불 수금액의 최댓값]을 6으로 설정한다면  ① → ② →③,  ① → ④ → ⑤ →③ 두경로 모두 가능하기 때문에 이분탐색 함수는 true를 반환합니다.

그러나 [경로 중 지불 수금액의 최댓값]을 5로 설정한다면  ① → ② →③,  ① → ④ → ⑤ →③ 두경로 모두 불가능하기 때문에 이분탐색 함수는 false를 반환합니다.

 

해당 문제에서 최소 수금액은 1, 최대 수금액은 10^9입니다. 

따라서 이분탐색의 left는 1, right는 10^9 + 1로 잡아줬습니다. right값이 10^9가 아닌 10^9 + 1인 이유는 돈이 부족해서 그 어떤 경로로도 이동할 수 없는 경우가 존재하기 때문입니다.

 

 

 

getRoute 함수는 [경로 중 지불 수금액의 최댓값]이 mid일 때 A->B로 C원을 가지로 이동 가능한지 여부를 반환합니다. 이는 우선순위큐로 구현한 다익스트라를 이용하여 구현하였습니다.

// 1. 경로 비용 중 최댓값이 mid 이하여야 한다.
// 2. 가진 비용으로 갈 수 있어야 한다.
bool getRoute(long long mid) {
	priority_queue<pair<long long, long long>> myPQ; // (비용, 정점)
	myPQ.push({ 0, A });
	cost[A] = { 0, };

	while (!myPQ.empty()) { // 비용이 적을수록 우선순위가 높다.
		long long cur = myPQ.top().second;
		long long distance = myPQ.top().first * -1;
		myPQ.pop();

		if (cur == B) break;
		if (cost[cur] < distance) continue; // 시간초과 방지

		for (int i = 0; i < myGraph[cur].size(); i++) {
			long long next = myGraph[cur][i];
			long long nextCost = myCost[cur][i];

			// 1. 경로 비용 중 최댓값이 mid 이하여야 한다.
			// 2. 가진 비용으로 갈 수 있어야 한다.
			if (nextCost <= mid && cost[cur] + nextCost <= C) {
				if (cost[next] > cost[cur] + nextCost) {
					cost[next] = cost[cur] + nextCost;
					myPQ.push({ -cost[next] , next });
				}
			}
		}
	}

	if (cost[B] == 1000000000000005) return false;
	else return true;
}

이때 아래 두가지 조건을 만족하는 최단 경로(최소 비용의 경로)를 찾습니다.

1. 경로 비용 중 최댓값이 mid 이하여야 한다.

2. 가진 비용으로 갈 수 있어야 한다.

 

if (cost[cur] < distance) continue; // 시간초과 방지

이때 해당 문제를 pass하기 위해서는 시간 초과 방지 코드를 넣어주어야 합니다.

 

// 1. 경로 비용 중 최댓값이 mid 이하여야 한다.
// 2. 가진 비용으로 갈 수 있어야 한다.
if (nextCost <= mid && cost[cur] + nextCost <= C) {
    if (cost[next] > cost[cur] + nextCost) {
        cost[next] = cost[cur] + nextCost;
        myPQ.push({ -cost[next] , next });
    }
}

이때 우선순위큐에는 같은 정점이라도 여러 비용을 갖는 상태가 삽입 될 수 있습니다.

그러나 결국 가장 최초로 pop되는 상태가 최소 비용입니다.(비용이 적은 것이 우선순위가 높다)

따라서 이후로 pop 되는 상태의 비용 distance는 cost[cur]보다 크게되고 해당 케이스의 경우 continue로 건너뛰게합니다.

 

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

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

using namespace std;

const int MAX = 100100;
long long N, M, A, B, C;

long long maxCost = -1;

vector<long long> myGraph[MAX];
vector<long long> myCost[MAX];

long long cost[MAX] = { 0, };

void checkInit() {
	for (int i = 0; i < MAX; i++) {
		cost[i] = 1000000000000005;
	}
}

// 1. 경로 비용 중 최댓값이 mid 이하여야 한다.
// 2. 가진 비용으로 갈 수 있어야 한다.
bool getRoute(long long mid) {
	priority_queue<pair<long long, long long>> myPQ; // (비용, 정점)
	myPQ.push({ 0, A });
	cost[A] = { 0, };

	while (!myPQ.empty()) { // 비용이 적을수록 우선순위가 높다.
		long long cur = myPQ.top().second;
		long long distance = myPQ.top().first * -1;
		myPQ.pop();

		if (cur == B) break;
		if (cost[cur] < distance) continue; // 시간초과 방지

		for (int i = 0; i < myGraph[cur].size(); i++) {
			long long next = myGraph[cur][i];
			long long nextCost = myCost[cur][i];

			// 1. 경로 비용 중 최댓값이 mid 이하여야 한다.
			// 2. 가진 비용으로 갈 수 있어야 한다.
			if (nextCost <= mid && cost[cur] + nextCost <= C) {
				if (cost[next] > cost[cur] + nextCost) {
					cost[next] = cost[cur] + nextCost;
					myPQ.push({ -cost[next] , next });
				}
			}
		}
	}

	if (cost[B] == 1000000000000005) return false;
	else return true;
}

long long solution() {
	long long l = 1, r = maxCost + 1;
	while (l < r) {
		long long mid = (l + r) / 2;

		checkInit();
		if (getRoute(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	if (r > maxCost) return -1;
	return r;
}


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

	cin >> N >> M >> A >> B >> C;

	for (int i = 0; i < M; i++) {
		long long first, second, cost;
		cin >> first >> second >> cost;
		myGraph[first].push_back(second);
		myGraph[second].push_back(first);

		myCost[first].push_back(cost);
		myCost[second].push_back(cost);

		if (cost > maxCost) maxCost = cost;
	}

	checkInit();
	cout << solution();

	return 0;
}