백준 1939 중량제한 (파이썬)

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

1939번: 중량제한

1. 양방향으로 중량을 함께 저장한다

2. 중량은 1부터 목적지로 올 수 있는 중량 중에서 최대값 까지 올 수 있으므로 이를 이분탐색의 범위로 설정

3. left와 right의 중간값을 옮길 중량으로 해서 목적지까지 도달할 수 있는지 bfs로 검증하면서 이분탐색 실행

from collections import deque
import sys

input = sys.stdin.readline

def bfs(x, th):
    q = deque()
    c = [0 for _ in range(n)]
    q.append(x)
    c[x] = 1
    while q:
        x = q.pop()
        for nx, w in a[x]:
            if c[nx] == 0 and w >= th:
                c[nx] = 1
                q.append(nx)

    if c[y-1] == 1:
        return 1
    else:
        return 0

n, m = map(int, input().split())
a = [[] for _ in range(n)]

for _ in range(m):
    x, y, w = map(int, input().split())
    a[x-1].append([y-1, w])
    a[y-1].append([x-1, w])

x, y = map(int, input().split())

left, right = 1, 0
for i in a[y-1]:
    right = max(right, i[1])

while left <= right:
    mid = (left + right) // 2
    if bfs(x-1, mid):
        ans = mid
        left = mid + 1
    else:
        right = mid -1
print(ans)