[백준-1939] 중량제한

간단한 BFS + 이분탐색 문제였다.

일단 입력 값을 보았을 때, node 의 개수가 10000개에 다리의 개수가 10만개이다. 때문에 전체를 다 탐색하게 되면 시간 초과가 발생할 수 있다. 때문에 다음과 같은 로직으로 푸는게 안전하다.

• 최소, 최대 cost 값을 찾은 다음에 이분탐색으로 적절한 cost 값을 찾는다.
• 각 cost 값 마다 bfs 를 통해 start - finish 경로가 있는지 확인한다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

int check[100001];
int start, finished;
vector<pii> v[100001];

bool bfs(int cost) {
	queue<int> q;
	q.push(start);
	check[start] = 1;
	
	while(!q.empty()) {
		int cx = q.front();
		q.pop();
		
		if(cx == finished) {
			return true;
		}
		
		for(int i=0 ; i<v[cx].size() ; i++) {
			int tx = v[cx][i].first;
			int tval = v[cx][i].second;
			if(check[tx]) continue;
			if(cost > tval) continue;
			
			check[tx] = 1;
			q.push(tx);
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	
	int n, m;
	int a, b, c, cmax = 0;
	cin >> n >> m;
	
	
	for(int i=1 ; i<=m ; i++) {
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
		cmax = max(cmax, c);
	}

	cin >> start >> finished;
	int left = 0, right = cmax, mid;
	int nmax = 0;
	while(left <= right) {
		
		mid = (left + right) / 2;
		memset(check, 0, sizeof(check));
		if(bfs(mid)) {
			left = mid + 1;
			nmax = max(nmax, mid);
		}
		else {
			right = mid - 1;
		}
	}
	cout << nmax;
}

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

1939번: 중량제한