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

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

시간 제한 5초, 메모리 제한 512MB

# 조건

• 소싯적 호석이는 골목 대장의 삶을 살았다.
• 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다.
• 교차로의 번호는 1번부터 N 번까지로 표현한다.
• 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다.
• 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다.
• 수금하는 요금은 골목마다 다를 수 있다.
• 당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다.
• 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다.
• 하지만 이왕 지나갈 거면, 최소한의 수치심을 받고 싶다.
• 당신이 받는 수치심은 경로 상에서 가장 많이 낸 돈에 비례하기 때문에, 결국 갈 수 있는 다양한 방법들 중에서 최소한의 수치심을 받으려고 한다.
  • 즉, 한 골목에서 내야 하는 최대 요금을 최소화하는 것이다.

• 예를 들어, 위의 그림과 같이 5개의 교차로와 5개의 골목이 있으며, 당신이 1번 교차로에서 3번 교차로로 가고 싶은 상황이라고 하자.
• 만약 10원을 들고 출발한다면 2가지 경로로 갈 수 있다.
• 1번 -> 2번 -> 3번 교차로로 이동하게 되면 총 10원이 필요하고 이 과정에서 최대 수금액을 5원이었고, 1번 -> 4번 -> 5번 -> 3번 교차로로 이동하게 되면 총 8원이 필요하며 최대 수금액은 6원이 된다.
• 최소한의 수치심을 얻는 경로는 최대 수금액이 5인 경로이다.
• 하지만 만약 8원밖에 없다면, 전자의 경로는 갈 수 없기 때문에 최대 수금액이 6원인 경로로 가야 하는 것이 최선이다.
• 당신은 앞선 예제를 통해서, 수치심을 줄이고 싶을 수록 같거나 더 많은 돈이 필요하고, 수치심을 더 받는 것을 감수하면 같거나 더 적은 돈이 필요하게 된다는 것을 알게 되었다.
• 마을의 지도와 골목마다 존재하는 호석이가 수금하는 금액을 안다면, 당신이 한 골목에서 내야하는 최대 요금의 최솟값을 계산하자.
  • 만약 지금 가진 돈으로는 절대로 목표 지점을 갈 수 없다면 -1 을 출력하라.

입력

• 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다.
• 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 수금액이 공백으로 구분되어 주어진다.
• 같은 교차로를 잇는 골목은 최대 한 번만 주어지며, 골목은 양방향이다.

출력

• 호석이가 지키고 있는 골목들을 통해서 시작 교차로에서 도착 교차로까지 C원 이하로 가는 경로 중에, 지나는 골목의 요금의 최댓값의 최솟값을 출력하라.
  • 만약 갈 수 없다면 -1을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 500,000
• 1 ≤ C ≤ 1014
• 1 ≤ 골목 별 수금액 ≤ 109
• 1 ≤ A, B ≤ N, A ≠ B
• 골목이 잇는 교차로의 번호는 서로 다르다.

# 접근 방법

• 일반적인 다익스트라로 풀게 되면 TL을 받는 문제이다.
• 문제 이름처럼 조금 더 효율적으로 최소 비용을 찾는 방법을 고민해보았다.
• 골목의 정보가 주어질 때 각 골목이 가지고 있는 비용을 COSTs set에 저장해주고 list로 변환 후 정렬을 해준다.
• 이후 매개변수 탐색을 통하여 한 골목에서 내야하는 최대 요금의 최소값을 찾아준다.
• left <= right를 만족하는 동안 while문을 돌면서 mid = (left+right)//2를 통하여 중간 값을 잡아준다.
• dijkstra 함수에 costs[mid]값을 넣어준 후 다익스트라를 실행해준다.

def dijkstra(min_val):  
    q = []  
    heappush(q, (0, C, A))  
    dist = [float('inf')] * (N+1)  
    dist[A] = 0  
    while q:  
        max_val, now_money, node = heappop(q)  
        if node == B:  
            return max_val  
        for next_node, next_money in graph[node]:  
            money = now_money - next_money  
            val = max(max_val, next_money)  
            if val > min_val:  
                continue  
            if money >= 0:  
                if dist[next_node] > max_val:  
                    heappush(q, (val, money, next_node))  
                    dist[next_node] = max_val  
    return -1

• 현재까지의 한 골목의 최대 비용의 최솟값, 남은 돈, 현재 노드를 한 세트로 q에 넣어준다.
• 만약 도착지에 도착했다면, 현재 max_val을 return 해주고 아니라면 다음 목적지를 찾아준다.
• 이 때, 남은 돈이 부족하거나 현재 골목에서의 최대값이 기록된 값보다 크다면 continue를 해준다.
• 그렇지 않다면 q에 넣어주고 dist 배열에 최댓값을 갱신해준다.

전체 코드

import sys
sys.stdin = open('input.txt')
si = sys.stdin.readline
from heapq import heappop, heappush

def solve():
    def dijkstra(min_val):
        q = []
        heappush(q, (0, C, A))
        dist = [float('inf')] * (N+1)
        dist[A] = 0
        while q:
            max_val, now_money, node = heappop(q)
            if node == B:
                return max_val
            for next_node, next_money in graph[node]:
                money = now_money - next_money
                val = max(max_val, next_money)
                if val > min_val:
                    continue
                if money >= 0:
                    if dist[next_node] > max_val:
                        heappush(q, (val, money, next_node))
                        dist[next_node] = max_val
        return -1
    N, M, A, B, C = map(int, si().split())
    graph = [[] for _ in range(N+1)]
    costs = set()
    for _ in range(M):
        a, b, c = map(int, si().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
        costs.add(c)
    costs = sorted(list(costs))
    result = float('inf')
    left = 0
    right = len(costs) - 1
    while left <= right:
        mid = (left+right) // 2
        v = dijkstra(costs[mid])
        if not v == -1:
            result = min(result, v)
            right = mid - 1
        else:
            left = mid + 1
    print(result if not result == float('inf') else -1)
solve()