[백준] 20183번: 골목 대장 호석 - 효율성 2

문제

백준 - 20183번: 골목 대장 호석 - 효율성 2

분석

교차로와 골목, 수금액에 대한 정보가 주어졌을 때 내야하는 경로상 최대 요금의 최솟값을 구하는 문제이다.

처음에 단순히 다익스트라 알고리즘만을 이용해 예산을 넘지 않는 범위에서 최소 요금을 갱신해서 통과하지 못했다. 이렇게 하면 무조건 최소로 갱신하게 되는데 그 상황에서 최대보다, 다른 경로로 갔을 때 최대가 더 작을 수 있다. 이런 예외 상황을 이유로 경로상 최대 수금액을 고정하고 다익스트라 알고리즘을 진행해야 한다.

경로상 최대 수금액은 이분탐색으로 처리할 수 있다. 처음에 골목당 수금액을 따로 저장해둔 뒤, 정렬한다.
여기서 절반씩 범위를 좁히면서 mid를 넣고 다익스트라를 돌렸을 때 가능한 경우라면 최대 수금액을 더 줄여봐서 탐색할 수 있다. 가능하지 않을 경우 최대 수금액을 늘려서 탐색해야 한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from heapq import heappush, heappop
n, m, start, end, budget = map(int, input().split())
graph = [[] for _ in range(n+1)]
cost_arr = []
for _ in range(m):
    i, j, fee = map(int, input().split())
    graph[i].append((j, fee))
    graph[j].append((i, fee))
    cost_arr.append(fee)

INF = sys.maxsize
def dijkstra(maximum):
    cost = [INF]*(n+1)
    cost[start] = 0
    pq = []
    heappush(pq, (0, start))
    while pq:
        now_c, now = heappop(pq)
        if now_c > cost[now]:
            continue
        for nxt, nxt_c in graph[now]:
            if nxt_c <= maximum and cost[nxt] > now_c + nxt_c:
                cost[nxt] = now_c + nxt_c
                heappush(pq, (cost[nxt], nxt))
    return cost[end] <= budget

cost_arr.sort()
left, right = 0, len(cost_arr)-1
ans = INF
while left <= right:
    mid = (left+right)//2
    if dijkstra(cost_arr[mid]):
        ans = min(ans, cost_arr[mid])
        right = mid-1
    else:
        left = mid+1
print(ans if ans != INF else -1)

끝으로..
다익스트라와 이분탐색을 둘 다 활용하는 좋은 문제였다.