[백준]Baekjoon1939(이진탐색)

문제링크 : https://www.acmicpc.net/problem/1939

풀이

문제를 어떻게 풀까 하다가 이진탐색과 DFS를 결합하기로 하였다.

DFS같은 경우 경로를 따라 다리를 건널 때 DFS함수에 매개변수로 넣어준

하중이 다리가 견딜 수 있는 하중보다 높으면 다리를 못건너도록 하여

트럭이 목적지까지 가면 따로 지정해준 전역변수에 true를 할당하도록 하였고

목적지까지 가지 못한다면 false를 할당하도록 하였다.

나머지 과정은 그 true인지 false인지에 따라 처리를 달리해주며 무게에 따라

이진탐색을 계속 하도록 하였다.

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

using namespace std;

vector<pair<int, long long>> v[100001];
bool map[100001];
int start_point, end_point;
bool b;

void DFS(long long weight,int start)
{
	map[start] = true;
	if (start == end_point) {
		b = true;
		return;
	}
	for (int i = 0; i < v[start].size(); i++) {
		if (v[start][i].second >= weight && !map[v[start][i].first])
			DFS(weight, v[start][i].first);
	}
}

int main()
{
	int N, M;
	scanf("%d %d", &N,&M);

	int A, B;
	long long C;
	long long max = 0;
	while (M--) {
		scanf("%d %d", &A, &B);
		scanf("%lld", &C);

		v[A].push_back(make_pair(B, C));
		v[B].push_back(make_pair(A, C));
		if (C > max) max = C;
	}
	scanf("%d %d", &start_point, &end_point);
	long long first = 1; long long last = max;
	long long result = 0;
	while (first <= last)
	{
		memset(map, false, 100001);
		b = false;
		long long mid = (first + last) / 2;
		DFS(mid, start_point);
		if (b) {
			if (mid > result) result = mid;
			first = mid + 1;
		}
		else {
			last = mid - 1;
		}
	}
	printf("%lld\n", result);
}