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

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

# 중량제한
import sys
from collections import deque
MAX = sys.maxsize
input = sys.stdin.readline
N, M = map(int, input().split())

arr = [[] for _ in range(N+1)]
weight = [MAX] * (N+1)
for _ in range(M):
    a, b, cost = map(int, input().split())
    arr[a].append((b, cost))
    arr[b].append((a, cost))
start_city, arrive_city = map(int, input().split())


def bfs(mid):
    q = deque()
    q.append(start_city)
    visited[start_city] = True
    while q:
        now = q.popleft()
        if now == arrive_city:
            return True
        for nnow, ncost in arr[now]:
            if not visited[nnow]:
                if mid <= ncost:
                    visited[nnow] = True
                    q.append(nnow)
    return False


result = 0
start, end = 1, int(1e9)
while start <= end:
    visited = [False] * (N+1)
    mid = (start+end) // 2
    if bfs(mid):
        result = mid
        start = mid + 1
    else:
        end = mid - 1
print(result)

 

BFS, 이분탐색

1. start와 end를 C의 범위로 잡아준다 (1, 1000000000)

2. mid를 이용해서 bfs를 한다

    - bfs를 하면서 mid값이 시작도시(start_city)에서 도착도시(end_city)까지 가는 다리의 최대 중량보다 작으면 True

    - 아니면 False를 반환

3. True이면 mid가 조금더 커져야 된다. result에 저장해주고 start = mid +1

4. False이면 mid가 더 작아져야 된다. end = mid -1

5. result 출력

 

문제만 보고 다익스트라로 보고 달려들었다가 약점이었던 이분탐색으로 풀어보고자 했다.

풀고나니 백준에서는 에초에 이분탐색 문제로 분류했다...