[백준 1939] 중량제한 (C++)

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

 

문제

---

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

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

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

 

입력

---

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

 

출력

---

첫째 줄에 답을 출력한다.

 

문제 풀이

---

이분탐색을 이용한 문제.

이분탐색의 mid를 최대 중량이라 가정하고, 해당 중량으로 이동할 수 있는 도로가 있는지 BFS로 찾는다.

중량제한을 초과해서는 다리를 건널 수 없으므로 BFS 큐에 넣을 수 있는 조건은 이미 방문한 섬이 아니면서, 지나갈 도로의 중량제한이 mid보다 크거나 같아야 한다.

탐색 도중 공장이 있는 섬에 방문하면 해당 중량으로 이동할 수 있는 것이다. 이 무게보다 더 큰 값으로 이동할 수 있는지 left=mid+1로 무게를 늘려 확인한다.

큐가 다 빌 때까지 공장이 있는 섬에 방문하지 못하면 해당 중량으로는 이동할 수 없다. right=mid-1로 중량을 줄여 더 작은 값으로는 이동할 수 있는지 확인한다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
int factoryA, factoryB;
vector<pair<int, int>>* bridges;
bool* isVisited;
int answer = 0;
queue<int> bfsQueue;

void reset()
{
	for (int i = 0; i < N; i++)
	{
		isVisited[i] = false;
	}
	while (!bfsQueue.empty())
	{
		bfsQueue.pop();
	}
}

bool canMove(int weight)
{
	reset();
	isVisited[factoryA-1] = true;
	bfsQueue.push(factoryA-1);
	while (!bfsQueue.empty())
	{
		int currentIsland = bfsQueue.front();
		if (currentIsland == factoryB-1)
		{
			return true;
		}
		for (int i = 0; i < bridges[currentIsland].size(); i++)
		{
			pair<int, int> nodeInfo = bridges[currentIsland].at(i);
			if (isVisited[nodeInfo.first] == false && nodeInfo.second >= weight)
			{
				isVisited[nodeInfo.first] = true;
				bfsQueue.push(nodeInfo.first);
			}
		}
		bfsQueue.pop();
	}
	return false;
}

void binarySearch(int left, int right)
{
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (canMove(mid) == true)
		{
			answer = max(answer, mid);
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
}

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

	int a, b, w;
	cin >> N>>M;
	bridges = new vector<pair<int, int>>[N];
	isVisited = new bool[N];
	for (int i = 0; i < N; i++)
	{
		isVisited[i] = false;
	}
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b >> w;
		bridges[a - 1].push_back(pair(b - 1, w));
		bridges[b - 1].push_back(pair(a - 1, w));
	}
	cin >> factoryA >> factoryB;
	binarySearch(1, 1000000000);
	cout << answer << "\n";
	return 0;
}