[BOJ]백준 20168/20182/20183번: 골목 대장 호석(기능성, 효율성)(C++)/Dijkstra, 이진탐색

www.acmicpc.net/problem/20168

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

www.acmicpc.net/problem/20182

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

www.acmicpc.net/problem/20183

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

오늘 모의코테 하면서 풀었던 골목 대장 호석 문제

다익스트라와 이진탐색을 조합해서 풀 수 있는게 신선했고 좋은 문제인 것 같아서 정리해야겠다고 생각했다 🥺

 

기능성 문제(20168)번은 일반 다익스트라+브루트 포스

효율성 1 문제(20182)번은 다익스트라+이진탐색

효율성 2 문제(20183)번은 parameter가 3개인 다익스트라

로 풀이했다!! 사실 가장 빠른 코드는 효율성2번에서 풀었던 코드이지만 이진탐색을 응용해볼 수 있는 20182번 코드도 좋았다

이진탐색의 parameter는 [지나는 골목 요금의 최대값]으로 설정해서, 다익스트라 함수에서 해당 edge weight를 초과하는 경우에는 지나갈 수 없게 설정해주고 b vertex에 도달할 수 있는지 검사해주었다

 

while문이 종료될 때 까지 loop invarient를 만족하므로 left+1=right이면서 dijkstra(left)=false&dijkstra(right)를 만족하는 right값을 찾아주면 되는 문제였다

 

20168, 20182 코드(C++)

#include <bits/stdc++.h>
#define pii pair<int,int>
#define INF 987654321
using namespace std;

int n, m, a, b, c;
vector<vector<pii>> g;

bool dijkstra(int k) {	//지나갈 수 있는 최대 수치심(edge weight)
	vector<int> dist(n + 1, INF);
	vector<bool> visit(n + 1, false);

	visit[a] = true;
	dist[a] = 0;

	priority_queue<pii> pq;	//dist, vertex의 element를 가진 priority queue(dist 오름차순)
	pq.push(make_pair(0,a));

	while (!pq.empty()) {
		int cur = pq.top().second; pq.pop();

		visit[cur] = true;
        if(cur==b) return dist[b]<=c;	//c이하로 b vertex를 갈 수 있는지 반환
		for (auto x : g[cur]) {	//cur와 연결된 다음 vertex에 대해
			if (visit[x.second]||(x.first>k))continue;	//만약 해당 vertex와 연결시켜주는 edge의 weight가 k를 넘으면 지나갈 수 없음
			if (dist[x.second] > dist[cur] + x.first) {
				dist[x.second] = dist[cur] + x.first;
				pq.push(make_pair(-dist[x.second], x.second));	//dist기준 min heap으로 만들어주기 위해 -1을 곱한 뒤 push
			}
		}
	}
	return false;
}

int main() {
	scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
	g = vector<vector<pii>>(n + 1, vector<pii>());

	for (int i = 0,u,v,w; i < m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back(make_pair(w, v));
		g[v].push_back(make_pair(w, u));
	}

	int left = -1,right=21;
    //loop invarient
    // 1. left<right
    // 2. dijkstra(left) = false & dijkstra(right) = true
	while (left + 1 < right) {
		int mid = (left + right) / 2;
		if (dijkstra(mid))
			right = mid;
		else left = mid;
	}
	printf("%d", right==21?-1:right);
	return 0;
}

20183 코드(C++)

#include <bits/stdc++.h>
#define ull unsigned long long
#define pli pair<ull,int>
#define pii pair<int,int>
using namespace std;

int n, m, a, b,ans;
ull c;
vector<vector<pii>> g;
typedef struct {
	int e;
	ull c;
	int n;
}rhs;
struct compare{
	bool operator()(rhs a, rhs b) {
		return a.e > b.e;
	}
};

int main() {
	scanf("%d%d%d%d%lld", &n, &m, &a, &b, &c);
	g = vector<vector<pii>>(n + 1, vector<pii>());

	for (int i = 0,u,v,w; i < m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back(make_pair(w, v));
		g[v].push_back(make_pair(w, u));
	}
	   
	vector<int> cost(n + 1, INT_MAX);
	vector<bool> visit(n + 1, false);

	visit[a] = true;
	cost[a] = 0;

	priority_queue< rhs, vector<rhs>, compare > pq;
	pq.push({ 0,0,a });

	while (!pq.empty()) {
		auto cur = pq.top();
		pq.pop();

		visit[cur.n] = true;
		for (auto x : g[cur.n]) {
			int emb = max(cur.e, x.first);
			ull ndist = cur.c + x.first;
			if (!visit[x.second] && (cost[x.second] > emb) && (ndist <= c)) {
				cost[x.second] = emb;
				pq.push({ emb,ndist,x.second });
			}
		}
	}
	printf("%d", cost[b] == INT_MAX ? -1 : cost[b]);

	return 0;
}