[C++][백준] 중량제한(1939) - 이분탐색

문제

N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

 

출력

첫째 줄에 답을 출력한다.

 

풀이

이분탐색을 이용하여 풀이하였습니다.

이분탐색을 통해 우리가 구해야 하는 답은 (TARGET - 1) 입니다.

위 예시를 적용해보면 (TARGET - 1)은 3입니다.

이 값은 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값입니다.

 

getRoutebinary_search() 함수는 [물품의 중량]이 mid일 때 섬 from에서 섬 to로 이동 가능한지 여부를 반환합니다. 이는 큐를 이용하여 구현하였습니다.

 

전체 코드는 아래와 같습니다.

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

int N, M;
const int MAX = 10010;
vector<int> myGraph[MAX];
vector<int> myCost[MAX];

int from, to;
bool visited[MAX];

void init() {
	for (int i = 1; i <= N; i++) {
		visited[i] = false;
	}
}

// 물품의 중량이 n일 경우 from → to 옮길 수 있는가
bool possible(int n) {
	init();

	queue<int> myQueue;
	myQueue.push({ from });
	visited[from] = true;

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

		for (int i = 0; i < myGraph[cur].size(); i++) {
			int next = myGraph[cur][i];
			int nextMAX = myCost[cur][i];

			if (visited[next] == false && n <= nextMAX) {
				visited[next] = true;
				myQueue.push({ next });
			}
		}
	}

	if (visited[to] == true) {
		return true;
	}

	return false;
}

int binary_search() {
	int l = 1, r = 1000000001;

	while (l < r) {
		int mid = (l + r) / 2;

		if (possible(mid)) {
			l = mid + 1;
		}
		else {
			r = mid;
		}
	}
	return r - 1;
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int island1, island2, cost;
		cin >> island1 >> island2 >> cost;

		myGraph[island1].push_back(island2);
		myGraph[island2].push_back(island1);
		myCost[island1].push_back(cost);
		myCost[island2].push_back(cost);
	}
	cin >> from >> to;

	cout << binary_search();

	return 0;
}