[Python] boj no. 1939 : 중량제한

Problem

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

Idea

시작 지점부터 도착 지점까지 실을 수 있는 물건의 최대 중량을 구하는 문제.

우선, 임의의 무게 W를 싣고 도착 지점까지 도착할 수 있는지는 다리를 건널 때마다 다리의 무게 제한과 W를 비교하면서 BFS 하는 것으로 구할 수 있다.

BFS의 결과는 True 혹은 False, 두 가지 결과만 나오므로 W에 대해 True일 경우 mid의 오른편, False의 경우 왼편의 리스트를 대상으로 이분 탐색한다. 또한, 탐색을 반복하여도 left의 값은 작아지지 않으므로 BFS의 결과가 True가 나왔을 때마다 중량제한 값을 최신화한다.

Code

import sys
from collections import deque

def bfs(weight):
    visited = [False for _ in range(N+1)]
    visited[start] = True
    queue = deque([start])
    
    while queue:
        cur = queue.popleft()
        visited[cur] = True
        
        if cur == end:
            return True
        
        for node, limit in graph[cur]:
            if not visited[node] and weight <= limit:
                queue.append(node)
                visited[node] = True
    
    return False

input = lambda : map(int, sys.stdin.readline().split())

N, M = input()
graph = [[] for _ in range(N+1)]
for _ in range(M):
    A, B, C = input()
    graph[A].append((B, C))
    graph[B].append((A, C))
    
start, end = input()
left, right = 1, 1000000000
result = -1
while left <= right:
    mid = (left + right) // 2
    
    if bfs(mid):
        result = mid
        left = mid + 1
    else:
        right = mid - 1
              
print(result)

Comment