백준 1939번: 중량제한

[문제 링크]

1939번: 중량제한

---

그래프 탐색과 이분 탐색을 활용하는 문제였다.

공장이 있는 두 섬 A, B가 있다고 할 때, 중량을 견딜 수 있는 다리만 이용하여 A와 B를 왕래할 수 있는지 체크하기 위해 bfs를 이용하였다.

최대 중량을 구하기 위해 여러번의 bfs 탐색을 수행해야 하는데, 중량 C의 최대값이 10억으로 매우 크기 때문에 1~10억까지 전부 시도해보는 것이 아닌 이분 탐색을 활용하여 탐색 횟수를 최소화하였다.

 

추가로 섬의 개수 N이 최대 10000이므로, 그래프를 인접 행렬로 구현하게 되면 공간복잡도가 매우 커질 것이기에 인접리스트로 구현하여 공간복잡도를 줄였다.

---

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int N, M;
vector<pair<int, int>> adj[10001];
bool visited[10001];

bool dfs(int start, int end, int weight) {
	if (start == end) return true;
	visited[start] = true;

	for (auto x : adj[start]) {
		int next = x.first;
		int bridge = x.second;

		if (bridge >= weight && !visited[next]) {
			if (dfs(next, end, weight))
				return true;
		}
	}

	return false;
}

bool bfs(int start, int end, int weight) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

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

		if (here == end)
			return true;

		for (auto x : adj[here]) {
			int next = x.first;
			int bridge = x.second;

			if (bridge >= weight && !visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}

	return false;
}

int getMaximumWeight(int factory1, int factory2) {
	int start = 1;
	int end = 1000000000;

	int ret = 0;

	while (start <= end) {
		memset(visited, false, sizeof(visited));

		int mid = (start + end) / 2;

		if (bfs(factory1, factory2, mid)) {
			start = mid + 1;
			ret = mid;
		}
		else
			end = mid - 1;
	}

	return ret;
}

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

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		adj[A].push_back({ B,C });
		adj[B].push_back({ A, C });
	}

	int factory1, factory2;
	cin >> factory1 >> factory2;

	cout << getMaximumWeight(factory1, factory2) << endl;

	return 0;
}