[백준(BOJ)] 1939번 중량제한 - 파이썬/python

문제

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

1939번: 중량제한

N개의 섬과 몇 개의 섬 사이에 다리가 설치되어 있다. 각 다리에는 중량 제한이 있어서 물품을 옮길 때 제한을 초과하지 않아야 한다. 두 개의 섬에 공장을 세우고 최대한 많은 물품을 옮길 수 있는 최댓값을 구하는 문제다. 

예시

Example 1:

Input: 3 3
       1 2 2
       3 1 3
       2 3 2
       1 3
Output: 3

풀이

from collections import deque
import sys
input = sys.stdin.readline

def bfs(weight):
    q = deque()
    q.append(num1)
    visited = [False] * (n + 1)
    visited[num1] = True

    while q:
        now = q.popleft()

        for node, w in bridges[now]:
        # 현재 중량으로 건널 수 있는 다리만 탐색
            if not visited[node] and w >= weight:
                visited[node] = True
                q.append(node)
                
   # num2 에 도달할 수 있는 지 반환
    if visited[num2]:
        return True
    else:
        return False


n, m = map(int, input().split())
bridges = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    bridges[a].append([b, c])
    bridges[b].append([a, c])

# 공장이 위치한 두 섬
num1, num2 = map(int, input().split())

start = 0
end = int(1e9)

result = 0
while start <= end:
    mid = (start + end) // 2
	
    # 중량(mid)으로 num1 에서 num2 까지 도달 가능한지 확인
    if bfs(mid):
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

 

- 이 문제는 이분 탐색과 너비 우선 탐색을 활용하여 풀어준다.

- bfs 함수를 통해 주어진 중량을 기준으로 두 섬의 경로가 존재하는지 확인한다.

- 이분 탐색을 진행하면서 최적의 중량을 찾는다.

- 최종적으로 공장이 있는 두 섬을 연결하는 경로에서 옮길 수 있는 물품들의 최대 중량을 출력한다.