BaekJoon 1939번: 중량제한(C++)

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

1939번: 중량제한

풀이법

1) 단순 bfs로 문제를 풀고자 했더니 문제가 많이 생겼어서, 검색을 해서 풀어낸 문제이다.

2) 이분 탐색과 함께 bfs를 이용해서 풀 수 있는 문제였기에 공식처럼 bfs 문제를 풀던 것을 반성할 수 있는 문제였다.

3) 이분 탐색을 통해 나온 mid 값 이상인 무게를 지닌 트럭이, 시작점부터 종착점까지 갈 수 있는지를 bool 형태의 bfs() 함수로 나타내어 가능한 경우 low=mid+1을 시켜주었고, 갈 수 없는 경우는 high=mid-1을 시켜줌으로서 가장 큰 값을 찾을 수 있었다.

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m;
int ans=0;
vector<pair<int, int>> vec[10001];// [] 2차원 행은 가변 열은 고정
int start, theEnd;
vector<bool> visited(10001);
bool bfs(int weight)
{
	visited[start] = true;
	queue<int> q;
	q.push(start);
	while (!q.empty())
	{
		int nowX = q.front();
		q.pop();
		if (nowX == theEnd)
			return 1;
		for (int i = 0; i < vec[nowX].size(); i++)
		{
			int nextX = vec[nowX][i].first;
			int nextVal = vec[nowX][i].second;
			if (!visited[nextX] && nextVal >= weight)
			{
				visited[nextX] = true;
				q.push(nextX);
			}
		}
	}
	return 0;
}
void binarySearch() {
	int low = 0;
	int high = ans;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		for (int i = 0; i <= n; i++)
		{
			visited[i] = false;//초기화
		}
		if (bfs(mid) == true)
			low = mid + 1;
		else
			high = mid - 1;
	}
	cout << high;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		vec[a].push_back({ b,c });
		vec[b].push_back({ a,c });
		ans = max(ans, c);
	}
	cin >> start >> theEnd;
	binarySearch();
}