[Python/Baekjoon] 1939. 중량제한

💬 문제

문제 난이도: 백준 골드 3

문제 링크: https://www.acmicpc.net/problem/1939

❗️접근 방법

• 시작점에서 끝점까지 갈 때 싣고 갈 수 있는 최대 중량을 묻는 문제이다.
• 시작점부터 끝점까지 여러 다리를 건너는 경우가 생길 것이고, 이때에는 제일 무게 제한이 낮은 것이 싣고 갈 수 있는 최대 중량이 될 것이다. (min 사용)
• 시작점부터 끝점까지 가는 경로가 1개 이상 나올텐데 그 중에서는 최대이어야 한다. (maxHeap 사용)

✅ 정답 코드

# 중량제한 # 중량의 최댓값 #maxHeap
import sys, heapq
input = sys.stdin.readline
print = sys.stdout.write

N, M = map(int, input().split(' '))
graph = [[] for _ in range(N+1)]
for _ in range(M):
    one, two, limit = map(int, input().split(' '))
    graph[one].append((limit, two))
    graph[two].append((limit, one))
start, end = map(int, input().split(' '))
visited = [0 for _ in range(N+1)]

def dijkstra():
    H = []
    heapq.heappush(H, (-sys.maxsize, sys.maxsize, start))
    while H:
        _,nowLimit, nowNode = heapq.heappop(H)
        if nowNode == end:
            return str(nowLimit)
        for nextLimit, nextNode in graph[nowNode]:
            if visited[nextNode] < min(nextLimit, nowLimit):
                visited[nextNode] = min(nextLimit, nowLimit)
                heapq.heappush(H, (-visited[nextNode],visited[nextNode], nextNode))
            
print(dijkstra())

✍️ 헷갈렸던 부분

• 시작점부터 끝점까지 가는 과정에서는 최솟값을 구해야하고
• 끝점에 도달했을 때에 얻게 되는 결과값들 중에서는 최댓값을 구해야 하기 때문에 minHeap을 써야 할지, maxHeap을 써야 할지 헷갈렸다.
• 결과적으로 얻고 싶은 것은 시작점에서 끝점에 도달했을 때의 최댓값이기 때문에 maxHeap을 사용하고,
• 일반적인 최소 비용을 구하는 다익스트라와 다르게 거쳐온 다리의 제한 중 가장 작은 값으로 갱신하는 식으로 코드를 짜면 되는 문제였다.