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

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MaxNum = 100001;
int n, m, start, finish;

bool visited[MaxNum];
vector<pair<int, int>> nodes[MaxNum];

bool BFS(int cost);

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int lowCost, highCost, maxCost;


	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int temp1, temp2, temp3;
		cin >> temp1 >> temp2 >> temp3;
		nodes[temp1].push_back({ temp2, temp3 });
		nodes[temp2].push_back({ temp1, temp3 });
		maxCost = max(maxCost, temp3);
	}
	cin >> start >> finish;

	lowCost = 0; highCost = maxCost;
	while (lowCost <= highCost)	//이진 탐색
	{
		memset(visited, false, sizeof(visited));

		int midCost = (lowCost + highCost) / 2;

		if (BFS(midCost) == true)
		{
			lowCost = midCost + 1;
		}
		else
		{
			highCost = midCost - 1;
		}
	}

	cout << highCost;
}

bool BFS(int cost)	//너비 우선 탐색
{
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty())
	{
		int currNode = q.front();	//현재 너비에 있는 것을 순차적으로 검색
		q.pop();	//검색한 곳은 삭제

		if (currNode == finish) return true;

		for (int i = 0; i < nodes[currNode].size(); i++)
		{
			int nextNode = nodes[currNode][i].first;
			int weight = nodes[currNode][i].second;

			if (!visited[nextNode] && cost <= weight)	//방문한 곳이 아니고 cost가 가중치보다 적을때
			{
				visited[nextNode] = true;
				q.push(nextNode);	//다음 너비에 있는 노드들을 저장
			}
		}
	}

	return false;
}

 

중량의 최대최소는 이진탐색으로 찾고 건너는 다리는 너비우선탐색을 하며 하나씩 검사한다.