백준 1939번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 3

---

풀이

 장염도 거의 다 나았으니 다시 할일을 시작해야겠다. 오랜만에 밀린 문제 정리하기이다.

 

 이 문제는 정말 인상적인 문제이다. 최단경로 문제같으면서도, 최단경로 문제라기엔 조금 어색한 문제이기 때문이다. 이 문제가 인상적이라고 느낀 이유는 그래프 탐색과 이분탐색을 섞은 문제이기 때문이다. 어떤 그래프에 대해 답이 a라고 한다면, a보다 작은 a'로도 해당 그래프를 통과할 수 있고, 무엇보다 다리의 중량제한이 최대 10억으로 매우 크다. 탐색의 범위가 넓고, 특정 값 기준으로 가능/불가능이 나뉘어지기 때문에 이분탐색을 사용하기 좋다.

 

 이분탐색을 통해 특정한 중량을 정하고, 해당 중량으로 그래프를 통과할 수 있는지 bfs를 돌리면서 최댓값을 찾으면 된다. 

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int>>> graph;
int n, st, ed;

void input() {
	int m, a, b, d;
	cin >> n >> m;
	graph.resize(n + 1);
	while (m--) {
		cin >> a >> b >> d;
		graph[a].push_back({d, b});
		graph[b].push_back({d, a});
	}
	cin >> st >> ed;
}

bool bfs(int weight) {
	queue<int> q;
	vector<bool> visited(n + 1);
	
	visited[st] = true;
	q.push(st);

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

		for(auto& [nxt_cost, nxt_pos] : graph[cur]) {
			if (nxt_cost < weight) continue;
			if (visited[nxt_pos]) continue;

			visited[nxt_pos] = true;
			q.push(nxt_pos);
		}
	}
	return visited[ed];
}

void sol() {
	int low = 1, high = 1e9 + 1, mid;
	while(low <= high) {
		mid = (low + high) / 2;
		if (bfs(mid)) {
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	cout << high;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}