[백준] 1939번 중량제한 [Python]

• 문제 : https://www.acmicpc.net/problem/1939
• 이분탐색 and BFS

from collections import defaultdict, deque

n, m = map(int, input().split()) # 섬 개수, 다리 정보 개수

graph = defaultdict(list)

maxValue = 0    # 다리들 중 최대 중량 변수

for i in range(m):
    a, b, c = map(int, input().split()) # 섬 <-> 섬 , 중량제한
    graph[a].append((b, c))
    graph[b].append((a, c))
    maxValue = max(maxValue, c)

p1, p2 = map(int, input().split()) # 공장 위치

def bfs(mid):
    Q = deque([graph[p1]])
    visit = [0] * (n+1)
    visit[p1] = 1

    while Q:
        next = Q.popleft()

        for node, kg in next: # 다음 경로 탐색
            if node == p2 and kg >= mid: # 공장에 도착 and 무게까지 통과하면
                return True
            
            if kg >= mid and visit[node] == 0:  # 다리를 건널 수 있으면
                Q.append(graph[node])   # 큐에 경로 추가
                visit[node] = 1
       
    return False    # 공장에 도착 못했을 때
        
l = 1
r = maxValue

while l <= r: # 이분탐색으로 최대 무게를 조절
    mid = (l+r) // 2
    answer = bfs(mid)   # bfs 시작

    if answer == False: # 공장까지 도착 X
        r = mid - 1     # 무게를 줄인다.
    elif answer == True: # 공장까지 도착 O
        l = mid + 1     # 무게를 늘린다.

print(r)