백준 1939 : 문제링크

  • 문제유형 :

    • 탐색

    • 이진탐색

    • BFS

  • 설명

    • 다리의 개수 M의 최대 100,000, 중량 제한 C는 최대 1,000,000,000

    • 이진탐색을 이용하면 시간 복잡도는 O(M * logC)

    • DFS로 도착지에 옮길 수 있는 지 확인

    • 한 번에 옮길 수 있는 물품의 최대값을 이진탐색으로 찾아낸다.

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    from collections import deque

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

    def bfs(c):
        queue = deque([start_node])
        visited = [False] * (n + 1)
        visited[start_node] = True
        while queue:
            x = queue.popleft()
            for y, weight in adj[x]:
                if not visited[y] and weight >= c:
                    visited[y] = True
                    queue.append(y)
        return visited[end_node]

    start = 1000000000
    end = 1

    for _ in range(m):
        x, y, weight = map(int, input().split())
        adj[x].append((y, weight))
        adj[y].append((x, weight))
        start = min(start, weight)
        end = max(end, weight)

    start_node, end_node = map(int, input().split())

    result = start
    while(start <= end):
        mid = (start + end) // 2
        if bfs(mid):
            result = mid
            start = mid + 1
        else:
            end = mid - 1

    print(result)