[백준] 1939번 : 중량제한

1939번: 중량제한

1939번: 중량제한

🤔 문제분석

데이크스트라를 활용하여 문제를 풀면 된다. 간선을 입력받을때에 다 입력받은 뒤에 무게를 기준으로 내림차순 정렬한다. 그 이유는 탐색을할때에 가장 무게가 많이 나가는 다리부터 방문을 해 나아가야 하기때문이다.

첫번째 섬으로부터 시작하여 가장 무게가 많이 나가는 다리부터 방문해나아가면서 방문값을 갱신해 나아간다. 방문을 해나아가면서 두번째 섬에 도착했을때는 방문을 종료하고 현재 값을 출력하고 종료한다.

💻 코드

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())

edge = [[] for _ in range(N+1)]

for _ in range(M):
    A, B, C = map(int, input().split())
    edge[A].append((B, C))
    edge[B].append((A, C))

for i in range(1, N):
    edge[i].sort(key=lambda x:-x[1])
            
start, end = map(int, input().split())
queue = []
heapq.heappush(queue, (0, start))

dp = [-1 for _ in range(N+1)]

while queue:
    cost, src = heapq.heappop(queue)
    cost = -1 * cost
    
    if src == end:
        print(cost)
        break
    
    if dp[src] > cost:
        continue
    
    dp[src] = cost
    
    for dst, n_cost in edge[src]:
        if cost == 0:
            dp[dst] = cost
            heapq.heappush(queue, (-n_cost, dst))
        else:
            n_cost = min(n_cost, cost)
            if n_cost > dp[dst]:
                heapq.heappush(queue, (-n_cost, dst))

🎯 피드백 및 개선사항

저번주에 이어서 자료구조 문제를 풀었습니다. 그러나 해당문제는 자료구조보다는 탐색과 정렬, 그리디 유형으로 생각이 듭니다 😀

데이크스트라를 이용하여 푸는것을 한번에 알게되었습니다. 문제의 힌트는 가장 무게가 많이 나가는 다리를 통하여 그리디한 방식으로 문제를 접근해야겠다는 생각이 들었습니다.