1939번: 중량제한 (탐색, 이분탐색, BFS) - Fastcampus

www.acmicpc.net/problem/1939

1939번: 중량제한

import sys
from collections import deque


# 이동가능한 물품중량 (mid) => 이분탐색
def search(N, SP, EP, start, end):
    res = 0

    while start <= end:
        mid = (start + end) // 2
        is_move = dfs(N, SP, EP, mid)  # 이동가능 여부

        if not is_move:
            end = mid - 1
        else:
            start = mid + 1
            res = mid

    return res


def dfs(N, SP, EP, weight):
    qu = deque([SP])
    visited = [0] * (N+1)

    while qu:
        node = qu.popleft()

        if not visited[node]:
            visited[node] = 1
            if node == EP:
                return True
            for e, w in graph[node]:
                if w >= weight:
                    qu.append(e)
    return False


N, M = map(int, input().split())

graph = [[] for _ in range(N + 1)]
min_w, max_w = 1e9, 0
for _ in range(M):
    x, y, w = map(int, sys.stdin.readline().split())
    graph[x].append((y, w))
    graph[y].append((x, w))
    min_w = min(min_w, w)
    max_w = max(max_w, w)

SP, EP = map(int, input().split())
print(search(N, SP, EP, min_w, max_w))