[Python] BOJ / 1939번 / 중량제한

1939번: 중량제한

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

풀이

문제를 첨 봤을 땐 다익스트라로 풀어도 될 것 같다는 생각이 들었다가 이 문제가 이분 탐색 문제로 분류됐다는 걸 깨닫고 최대한 이분 탐색으로 풀어보기 위해 고민했으나 마땅히 구현 방법이 떠오르지 않아 구글링을 통해 해결

 

막상 구현되어 있는 코드를 보니 이해하기 어려운 내용은 없었음

 

코드의 원리를 요약하자면 최소와 최대 중량을 정한다음 mid를 통해 중간값을 계산해서 BFS를 통해 목적지까지 도달할 수 있는지 없는지 확인하면서 mid 값을 이진탐색을 통해 조절해나가는 것

---

import sys
from collections import deque

input = sys.stdin.readline

# 해당 중량일 때 두 섬 사이로 물품을 옮길 수 있는지 확인
def bfs(mid):
    visited[start] = True   # 시작 섬
    que = deque()
    que.append(start)

    while que:
        now = que.popleft()

        if now == end:  # 도착 섬에 도달했다면
            return True # 해당 중량일 때 물품 이동이 가능하다는 것

        for nc, ni in bridge[now]:
            # 섬을 방문한 적이 없으며 다음 다리의 중량이 현재 물품의 중량보다 크거나 같을 때
            if not visited[ni] and mid <= nc:
                visited[ni] = True
                que.append(ni)
    
    return False    # 도착 섬에 도달하지 못한 경우

n, m = map(int, input().split())
bridge = [[] for _ in range(n + 1)]

# 다리 정보를 연결 리스트로 저장
for _ in range(m):
    a, b, c = map(int, input().split())
    bridge[a].append([c, b])
    bridge[b].append([c, a])

start, end = map(int, input().split())

# 중량 제한에 따라 내림차순 정렬
for i in range(1, n + 1):
    bridge[i].sort(reverse=True)

# 최소 중량과 최대 중량 초기화
left, right = 1, 1000000000

# 이분 탐색으로 최대 중량 찾기
while left <= right:
    visited = [False] * (n + 1)
    mid = (left + right) // 2

    if bfs(mid):    # 옮길 수 있는 중량인 경우
        left = mid + 1  # 중량을 더 올려봄
    else:           # 옮길 수 없는 중량인 경우
        right = mid - 1 # 중량을 더 내려봄

print(right)