[baekjoon 13905] 세부 (이분탐색 + BFS) (C++)

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

13905번: 세부

경로가 주어지고, 시작점 - 도착점까지 가는 경로의 가중치의 최솟값이 가장 큰 값을 구하는 문제이다.

예시 경로의 가중치가 4 - 2 - 4이면 이 경로의 최솟값은 2이다.

갈 수 있는 모든 경로 중 이 최솟값이 가장 큰 경우는?

 

처음엔 DFS + 백트래킹으로 모든 경로를 가면서, 최솟값을 저장했다. 하지만 시간 초과가 나왔다.

 

따라서 모든 경로를 가면서 최솟값을 직접 구하지 말고, 해당 경로의 최솟값을 미리 정해준 뒤에 해당 케이스가 최솟값을 만족하는 경우인지 판별했다.

즉, 최솟값을 구하는 문제 => 해당 최솟값을 만족하니? 의 Y/N 문제로 바꿨다.

그리고 그 과정에서 이분 탐색을 이용했다.

 

이분 탐색을 통해 최솟값을 정하고 => 그래프 탐색을 통해서 해당 최솟값을 만족하는 경로가 존재하나?

존재한다면, 최솟값을 더 높여서 다시 탐색

존재하지 않는다면, 최솟값을 낮춰서 다시 탐색

 

+ 추가로, 아예 목표 지점까지 가는 경로가 없는 케이스도 있다. 그 경우 0을 출력해야 정답이 나온다.

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;

typedef pair<int, int> pii;

int n, m, s, e, from, to, k, answer, mx;
vector<pii> v[100001];

bool BFS(int s, int e, int limit) {
	int check[100001] = { false, };
	queue<int> q;
	q.push(s);
	check[s] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		if (x == e)
			return true;

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int weight = v[x][i].second;

			if (!check[nx] && weight >= limit) {
				q.push(nx);
				check[nx] = true;
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> s >> e;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> k;
		v[from].push_back({ to, k });
		v[to].push_back({ from, k });
		mx = max(mx, k);
	}
	
	int left = 1;
	while (left <= mx) {
		int mid = (left + mx) / 2;

		if (BFS(s, e, mid)) {
			answer = mid;
			left = mid + 1;
		}
		else {
			mx = mid - 1;
		}
	}
	cout << answer;
}