[백준] 파이썬 1939 : 중량제한

 

 

# 한번의 이동에서 옮길 수 있는 중량의 최댓값
# 이분탐색으로 중량의 범위와 최대값을 찾고 bfs로 가능한지 확인한다 
from collections import deque
import sys
input = sys.stdin.readline

def bfs(weight): # weight = 중간값(최대 중량)
    queue = deque() # 큐
    queue.append(one) # 시작노드인 one부터 시작
    visited = [False] * (n + 1) # 방문확인
    visited[one] = True

    while queue:
        x = queue.popleft()
        for i, w in graph[x]: # 방문 가능한 섬들을 방문
            if not visited[i] and w >= weight: # 미방문 & 중량제한에 걸리지 않는다면
                visited[i] = True # 방문 확인 후 큐에 추가
                queue.append(i)
    if visited[two]: # 반복문이 끝난 뒤 도착지까지 도달했다면 true 리턴
        return True
    else:
        return False

n, m = map(int, input().split()) # 섬 개수
graph = [[] for _ in range(n+1)] # 다리. 그래프

for i in range(m): # 간선 연결
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

one, two = map(int, input().split()) # 공장이 있는 섬

start = 1 # 중량의 범위
end = 1000000000

result = 0 # 중량제한

while start <= end: # 이분탐색
    mid = (start + end) // 2
    if bfs(mid): # 중간값의 중량으로 도달할수있다면
        result = mid
        start = mid + 1 # 중량 더 늘리기
    else: #그럴수 없다면 중량 줄임
        end = mid - 1

print(result)

 

 

 

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

1939번: 중량제한