파이썬 백준 1939 중량제한

import sys
input = sys.stdin.readline
from collections import deque
 
Vn, En = map(int, input().split())
 
V = {}
upper = 1
lower = 1000000000
for i in range(1, Vn + 1) : 
    V[i] = []
for i in range(En) : 
    v1, v2, c = map(int, input().split())
    V[v1].append([v2, c])
    V[v2].append([v1, c])
    upper = max(upper, c)
    lower = min(lower, c)
start, end = map(int, input().split())
 
def BFS(weight) : 
    que = deque()
    que.append(start)
    gone[start] = True
    while que : 
        now = que.popleft()
        if now == end : 
            return True
        for next, limit in V[now] : 
            if not gone[next] and limit >= weight : 
                gone[next] = True
                que.append(next)
    return False
 
while upper >= lower : 
    gone = [False for i in range(Vn + 1)]
    center = (upper + lower) // 2
    if BFS(center) : 
        lower = center + 1
    else : 
        upper = center - 1
print(upper)
 

line 5 ~ 18

인풋을 받아 연결관계 dict V를 작성한다. 이분탐색의 upper, lower bound가 될 최대/최소 무게제한도 기록한다.

 

line 20 ~ 32

weight를 인풋으로 받는 함수 BFS를 정의한다.

간선의 비용(=무게제한)이 weight보다 클 때에만 이동하며 end에 도달가능한지 판별해 T/F를 리턴한다.

 

line 34 ~ 41

BFS의 인풋 weight를 upper, lower bound의 중간에서부터 시작해 범위를 좁혀나가는 이분탐색을 반복한다.

바운드가 교차했을 때 탐색을 멈추고 정답을 출력한다.