BOJ 1939 중량 제한

항해99 취업 리부트 알고리즘 2주차 시험 4번 문제

다익스트라 알고리즘으로 접근해서 풀었는데 제출 후에 이분 탐색으로도 다시 풀어봤다

log2 10억이 30미만 값으로 아주 작은 값일지라도 그 때마다 bfs든 dfs든 탐색이 진행되기 때문에 속도가 느릴줄 알았고, 불필요한 탐색이 발생하지 않는 다익스트라가 훨씬 빠를 거라고 생각했는데 아니었다.

생각해보면 다익스트라의 시간복잡도도 O((V+E) log V)고, bfs를 O(V+E) 이분 탐색을 O(log Weight)라고 하면 그렇게 크게 차이날 일도 아니었다. log V랑 log weight래봤자 어짜피 log 안의 값이니까... log V가 최대 13~14 이고 log weight가 최대 29~30이라면 엄청 차이날 일은 아니었지 싶다.

라고 하기엔 효율이 2배가량 차이 났어야하나. 적어도 BOJ 테스트 케이스에선 차이가 없다고 봐도 무방한 결과가 나왔다. 여하튼...

아래는 이분 탐색 소스코드

# 멘토님 추천 문제
# BOJ 1939 중량 제한
# binary search 사용

import sys
from collections import deque

input = sys.stdin.readline


def get_input():
    params = []

    n, m = list(map(int, input().split()))

    params.append(n)

    edges = [[] for _ in range(n)]

    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1

        edges[a].append([b, c])
        edges[b].append([a, c])

    p1, p2 = list(map(int, input().split()))

    params.append(p1 - 1)
    params.append(p2 - 1)
    params.append(edges)

    return params


def solution(params):
    # p1 출발지 p2 목적지
    n, p1, p2, edges = params

    def bfs(weight):
        q = deque()
        visited = [True for _ in range(n)]

        # 출발지 넣고 시작
        q.append(p1)
        visited[p1] = False

        while q:
            v = q.popleft()

            # 도착점이면 True return
            if v == p2:
                return True

            for edge in edges[v]:
                nv, nw = edge
                # 다리 제한 중량이 현재 무게보다 크거나 같으면 넘어가기
                if visited[nv] and nw >= weight:
                    visited[nv] = False
                    q.append(nv)
        # 도착점 못갔으면 False return
        return False

    def binary_search():
        left = 1
        right = 1_000_000_000

        while left <= right:
            mid = (left + right) // 2

            if bfs(mid):
                left = mid + 1
            else:
                right = mid - 1

        return left

    return binary_search() - 1


print(solution(get_input()))