[baekjoon 1939] 중량제한 (파라매트릭서치, BFS) (C++)

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

1939번: 중량제한

파라매트릭 서치와 BFS를 이용했던 문제로, 특정 무게를 버틸 수 있는 경로가 있는지 확인하는 문제였다.

 

고려해야 할 점은 다음과 같다.

1. 입력값으로 동일한 다리가 들어올 수 있다는 점 (1 2 4 / 1 2 7)

2. 가능한 중량의 최댓값을 골라야 하는데, 중량의 범위가 10억이라는 점

 

따라서, 중량 값을 먼저 정해두고 해당 중량 값을 pass 할 수 있는 경로가 있는지 확인을 하면 된다.

매번 이분 탐색을 진행하면서 해당 값을 버틸 수 있니? 를 물어보는 것이다.

 

중량 값을 먼저 정하는 것에서 이분 탐색을 이용했고, 경로가 있는지 확인하는 것에서 BFS를 이용했다.

추가적으로, 동일한 다리가 들어온다는 점에서 추가적으로 인접 리스트에 정렬을 사용했다.

 

5 8

1 2 4

1 2 7

1 3 5

1 4 4

2 5 4

2 5 7

3 5 1

4 5 4

1 5

의 테스트 케이스를 만들어 봤는데, 정답은 7인데 실제론 4가 나온다.

왜냐하면 BFS로 방문을 할 때, 1에서 2를 갈 때 7이라는 경로가 있지만 4라는 경로를 이용해서 방문을 하는 문제가 있기 때문이다.

그래서 우선적으로 큰 중량의 다리를 건너게 하기 위해서 내림차순으로 정렬을 했다.

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

int n, m, a, b, c, from, to, e, answer;
vector<pii> v[10001];

bool compare(pii a, pii b) {
	return a.second > b.second;
}

bool BFS(int from, int to, int limit) {
	queue<int> q;
	int check[10001] = { false, };
	q.push(from);

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (x == to) {
			return true;
		}

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

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

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
		e = max(e, c);
	}

	for (int i = 0; i < 10001; i++) {
		sort(v[i].begin(), v[i].end(), compare);
	}
	cin >> from >> to;

	int start = 1;
	while (start <= e) {
		int mid = (start + e) / 2;
		if (BFS(from, to, mid)) {
			answer = mid;
			start = mid+1;
		}
		else {
			e = mid-1;
		}
	}
	cout << answer;
}