[백준 20168, 20182, 20183] 골목 대장 호석 - 기능성, 효율성

문제

www.acmicpc.net/problem/20168

20168번: 골목 대장 호석 - 기능성

www.acmicpc.net/problem/20182

20182번: 골목 대장 호석 - 효율성 1

www.acmicpc.net/problem/20183

20183번: 골목 대장 호석 - 효율성 2

 

풀이

위의 문제들은 20183번 문제를 아래의 알고리즘을 통해 해결한 후, 나머지 문제들은 자료형(long long -> int)변환과 인접리스트 배열크기만 조절하여 결과적으로 모두 같게 풀었습니다. 같은 코드이기에 20183코드만 작성할게요 !

 

---

1. 시작 점으로부터 도착점까지 가는동안 내야하는 "최대 요금의 최솟값"을 구해야 하는데 이는 흔히 이분탐색에서 자주 나타나는 "최대의 최소화"꼴입니다.

 

2. 따라서 "최대 상한 요금이 X원일 때, 시작점으로부터 도착점까지 C원내로 갈 수있는가?"라는 결정함수를 작성해 이분탐색을 진행합니다. 이 때, 최대 상한 요금이 되는 후보들(cand)들은 실제 통행요금이고, 요금들을 벡터에 넣어주고나서 이분탐색이 문제없이 작동할 수 있도록 중복 제거를 해줍니다.

 

3. 결정함수내 도착점까지의 갈 수 있는지의 여부는 일반적인 다익스트라 알고리즘을 작성하여 해결할 수 있습니다.

 

코드 (20183) 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
#define all(x) (x).begin(), (x).end()
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
int N, M, a, b, u, v, w, l, r, m, cur, nxt;
ll c, cost, nxtdist, mav, ans;
vector<int> cand;
vector<pii> adj[100001];

bool cango(ll x) {
	vector<ll> dist(N + 1, inf);
	priority_queue<tuple<ll, int, int>> pq;
	pq.push({ 0,a,0 });
	while (!pq.empty()) {
		tie(cost, cur, mav) = pq.top(); pq.pop();
		cost *= -1;
		if (dist[cur] < cost) continue;
		for (pii i : adj[cur]) {
			nxt = i.first, nxtdist = cost + (ll)i.second;
			if (i.second <= x && dist[nxt] > nxtdist) {
				dist[nxt] = nxtdist;
				pq.push({ -nxtdist,nxt,max(mav,i.second) });
			}
		}
	}
	return (dist[b] <= c ? 1 : 0);
}

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

	cin >> N >> M >> a >> b >> c;
	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w }), adj[v].push_back({ u,w });
		cand.push_back(w);
	}
	sort(all(cand));
	cand.erase(unique(all(cand)), cand.end());
	r = cand.size() - 1, ans = -1;
	while (l <= r) {
		m = (l + r) / 2;
		if (cango(cand[m])) r = m - 1, ans = cand[m];
		else l = m + 1;
	}
	cout << ans;
}