중량 제한

1. 개요

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

2. 이진탐색 풀이

from collections import deque
import sys

def solution():
    INPUT = lambda: sys.stdin.readline().rstrip()
    READINTLIST = lambda: list(map(int, INPUT().split()))

    N, M = READINTLIST()
    BRIDGES = [READINTLIST() for _ in range(M)]
    G = [[] for _ in range(N+1)]
    START, END = READINTLIST()

    def graph():
        for a, b, c in BRIDGES:
            G[a].append((b, c))
            G[b].append((a, c))
    
    def bfs(weight):
        q, traced = deque(), set()

        traced.add(START)
        q.append(START)

        while q:
            node = q.popleft()

            for Next, limit in G[node]:
                if Next in traced or limit < weight:
                    continue

                if Next==END:
                    return True
                
                traced.add(Next)
                q.append(Next)

        return False

    def calcMaximum():
        right = 1000000000
        answer = left = 0

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

        return answer

    graph()
    return calcMaximum()

print(solution())