(Python3) - 백준(BOJ) 1939 : 중량 제한

https://www.acmicpc.net/problem/1939

dijkstra를 max heap으로 사용해본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

노드 개수 n, 간선 개수 m, 양방향 그래프 graph, 시작점 start와 도착점 end를 선언 후 적절히 입력 및 초기화해줍니다.

📔 풀이과정

어떤 경로에 최소 제한이 곧 이동 가능한 물품의 최대 하중이 됩니다. 따라서 max heap을 사용해 가장 큰 제한을 가진 노드들만 선택해 방문하도록 dijkstra를 구현해줍니다.1. 노드를 탐색할 변수 max_heap , 각 노드별 최대 하중 max_weight 배열을 선언 후 적절히 초기화합니다.

 

2. python에는 따로 max heap이 없으므로 원소를 저장할때 음수형태로 저장후 꺼내서 비교할 때 양수로 만들어줍니다.

 

3. 현 node에서 인접한 노드와 가중치를 확인하면서 다음을 진행합니다.

  3-1. next_weight 변수를 선언 현재까지의 무게와 next_node로 가기 위해 제한 무게를 비교했을 때 최솟값을 저장합니다. 다음 경로를 포함했을 때 물건이 이동 가능한 최대 무게가 되기 때문입니다.

 

  3-2. 만약 max_weight[next_node] 보다 next_weight가 크다면 무게를 늘려 이동 가능하므로 값을 갱신해주고 heap에 음수 가중치를 만들어 저장합니다.

 

📔 정답 출력 | 반환

도착했다면 가중치를 반환합니다.

---

📕 Code

📔 Python3

import heapq

n, m = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}

for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

start, end = map(int, input().split())

def dijkstra():
    max_heap = []
    heapq.heappush(max_heap, (-10**9, start))
    max_weight = [0] * (n+1)
    max_weight[start] = 10**9
    while max_heap:
        weight, node = heapq.heappop(max_heap)
        weight = -weight
        if node == end:
            return weight
        for next_node, limit in graph[node]:
            next_weight = min(weight, limit)
            if max_weight[next_node] < next_weight:
                max_weight[next_node] = next_weight
                heapq.heappush(max_heap, (-next_weight, next_node))
    return 0

print(dijkstra())

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.