[BOJ-1939] 중량제한 (C++)

백준 1939 중량제한

 

1939번: 중량제한

 

문제 설명

 

 - N개의 섬으로 이루어진 나라가 있다.

 

 - 섬들 사이에는 다리가 설치되어 차들이 다닐 수 있다.

 

 - 각 다리는 중량제한이 있기 때문에 물품을 옮길 수 있는 무게가 정해져있다.

 

 - 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너진다.

 

 - 한 번의 이동에서 옮길 수 있는 중량의 최대값을 구하라.

---

 

입력 값

 

 - 첫째 줄에 N, M이 주어진다.

   ( 1 <= N <= 10,000 / 1<= M <= 100,000 )

 

 - 다음 M개 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

   A번 섬과 B번 섬 사이에 중량 제한이 C인 다리가 존재한다는 의미이다. 

   ( 1 <= A, B <= N / 1 <= C <= 1,000,000,000 )

 

 - 모든 다리는 양방향이고, 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수 있다.

 

 - 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다.

 

 - 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

 

 

---

 

 

예제

---

 

 

문제 분석

 

 - 이 문제는 두 섬 사이에 옮길 수 있는 중량의 최대값을 구하는 문제이다.

 

 - 이 문제를 자세히 살펴보면, 옮길 수 있는 무게가 될 수 있는 값들이 연속적인 형태가 된다는 것이다.

   섬 A에서 섬 B로 옮길 수 있는 최대 중량이 100이라고 한다면, 1~99는 옮길 수 있고, 101~10억(최대)은 옮길 수 없다.

 

 - 정답이 될 수 있는 수들의 집합이 연속적인 형태를 가지고 있기 때문에 파라메트릭 서치를 사용할 수 있다.

파라메트릭 서치(Parametric Search)

 

 - 파라메트릭 서치를 이용하여 이 문제를 결정 문제로 변경할 수 있다.

 

 - 섬 사이 이동이 가능한 최대 무게를 구하라

   => 무게 X는 섬 사이 이동이 가능한가?

 

 - 무게 X를 최소값 1 부터 최대값 10억 까지 이분 탐색을 통해서 범위를 찾을 수 있다.

 

 - 즉, 파라메트릭 서치를 이용하면 시간복잡도는 O(Nlog(C)) = 10만 x log(10억) = 10만 x 30 = 300만

   최대 300만번의 연산을 통해 정답을 찾을 수 있다. 

 

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int N, M;

int start, last;

vector<pair<int,int>> boards[10001];

bool checkWeight(int s, int e, int weight) {

	bool visited[100001];
	
	fill_n(visited, 100001, false);

	queue<int> q;
	q.push(s);
	visited[s] = true;


	while (!q.empty()) {

		int now = q.front();
		q.pop();


		for (auto next : boards[now]) {
			int nextIndex = next.first;
			int nextCost = next.second;

			if (visited[nextIndex] || nextCost < weight) {
				continue;
			}

			if (nextIndex == e) {
				return true;
			}

			visited[nextIndex] = true;
			q.push(nextIndex);

		}

	}

	return false;


}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int s, e;

	
	cin >> N >> M;

	for (int i = 0; i < M; i++) {

		int a, b, c;
		cin >> a >> b >> c;

		boards[a].push_back({ b,c });
		boards[b].push_back({ a,c });
	}

	cin >> s >> e;

	int start = 1;
	int last = 1000000000;
	int result = 0;

	while (start <= last) {
		int mid = (start + last) / 2;

		bool check = checkWeight(s, e, mid);

		if (check) {
			result = max(result, mid);
			start = mid + 1;
		}
		else {
			last = mid - 1;
		}
	}

	cout << result << endl;


	return 0;
}