[백준 #1939] 중량 제한

1. 문제 설명

2. 해설

DFS/BFS와 이분 탐색을 같이 사용하는 문제. 잘 만든 문제라고 생각한다.

우선 중량제한의 최대값이 10억이기 때문에 이분 탐색으로 접근해야 한다. 어떻게 접근하면 좋을까?

1. left = 1, right = 입력받은 중량제한의 최대값으로 두고 시작한다.
2. mid값을 구하고, mid의 중량제한으로 지나갈 수 있는 경로가 있는지 DFS/BFS를 사용하여 찾아낸다.
3. 2번에서 찾은 경로가 있다면 result에 mid를 대입해주고, left = mid+1로 해준다.
4. 없다면 right = mid - 1로 해준다.
5. left <= right 동안 반복하고, 반복이 끝나면 result를 반환해준다.

3. 코드

from sys import stdin
from collections import deque, defaultdict
input = stdin.readline


def binary_search():
    left, right = 1, max_c
    res = 1

    while left <= right:
        mid = (left + right) // 2
        if bfs(mid):
            res = mid
            left = mid + 1
        else:
            right = mid - 1

    return res


# target 무게로 지나갈 수 있는 경로가 있는지 확인 
def bfs(target):
    queue = deque([start])
    visited = [0 for _ in range(N + 1)]
    visited[start] = 1

    while queue:
        node = queue.popleft()
        if node == end:
            return True

        for n, w in graph[node]:
            if not visited[n] and w >= target:
                visited[n] = 1
                queue.append(n)

    return False


N, M = map(int, input().split())

graph = defaultdict(list)
max_c = float('-inf')  # 중량 제한의 최대값

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])
    max_c = max(max_c, c)

start, end = map(int, input().split())
print(binary_search())