BOJ 13905 - 세부

문제

백준 온라인 저지 - 13905번

풀이 과정

시작 지점에서 목표 지점까지 이동할 때 필요한 간선의 최소 무게를 구하는 문제입니다.

중량제한 문제와 같은 유형이며 BFS + 이분 탐색 으로 해결할 수 있습니다.
이분 탐색 을 이용해 제한 무게를 정하고 해당 무게로 목표 지점에 도달할 수 있는지 BFS 로 판단하면 됩니다.

코드

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().split()))
S, E = list(map(int, sys.stdin.readline().split()))
bridges = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]


def make_graph():
    graph = [[] for _ in range(N + 1)]

    for frm, to, cost in bridges:
        graph[frm].append([to, cost])
        graph[to].append([frm, cost])

    return graph


def bfs(min_weight, graph):
    q = deque()
    visit = [0] * (N + 1)

    visit[S] = 1
    q.append(S)

    while q:
        here = q.popleft()

        if here == E:
            return True

        for there, cost in graph[here]:
            if min_weight <= cost and not visit[there]:
                visit[there] = 1
                q.append(there)

    return False


def solution():
    graph = make_graph()

    answer = 0
    lo, hi = 1, 1000000

    while lo <= hi:
        mid = (lo + hi) // 2
        is_possible = bfs(mid, graph)

        if is_possible:
            answer = mid
            lo = mid + 1
        else:
            hi = mid - 1

    return answer


print(solution())