Python - 알고리즘 실습 : 백준 <중량제한>

오늘은 다익스트라 알고리즘을 사용하는 백준 중량제한 문제를 알아보았다. 하지만 이번엔 최소 힙이 아닌 최대 힙을 이용하였다. 

백준 중량제한

1939번: 중량제한

아주 간단해보이는 중량제한 문제

1. 백준 중량제한

1) 문제 요약

(1) 섬들이 다리로 연결되어 있는데, 다리에는 중량제한이 있어 물품을 옮기는데 제한이 있다.

(2) 시작섬과 도착해야하는 섬이 주어질 때, 물품을 옮길 때 한 번 이동으로 옮길 수 있는 최대 중량을 구한다.

→ 최대 힙

 

2) 문제 해결

(1) 기존 최소 힙에서는 가중치를 0번째 index에 두고 해서 최소 비용, 거리를 구했지만 - 부호를 붙여 최대 힙으로 바꾼 후 pop할 때 - 부호를 다시 붙여준다.

최대 힙을 사용하는 이유는 중량이 큰 것부터 보면 최대 중량을 더 빠르게 구할 수 있기 때문이다.

   

    import heapq as hq

 

    def dijk(start, end):

        heap = []

        for i in arr[start]:

            hq.heappush(heap, (-i[0], i[1])) # 최대 힙

        while heap:

            w, f = hq.heappop(heap) # 중량, 시작점

            w = -w

            if f == end: # 시작점 == 끝점

                print(w)

                break

            if weight[f] > w: # 중량이 작으면 skip

                continue

            for nw, t in arr[f]: # 다음 지점까지의 중량과 다음 노드

                if weight[t] < nw and weight[t] < w: # 기존의 중량을 시작점에서 다음점 중량, 갖고 있는 중량과 비교

                    weight[t] = min(nw, w) # 시작점에서 다음점 중량과 갖고 있는 중량의 최솟값을 할당

                    hq.heappush(heap, (-weight[t], t))

 

 

(2) 인접 리스트로 받아준 후, 최대 중량을 기준으로 내림차순 정렬한다.

N 이 100,000이기 때문에 인접 행렬은 사용할 수 없어보인다.

   

    N, M = map(int, input().split()) # 노드 수, 간선 수

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

    for i in range(M): # 인접 리스트

        f, t, w = map(int, input().split())

        arr[f].append((w, t))

        arr[t].append((w, f))

    start, end = map(int, input().split()) # 시작점, 끝점

    for i in range(1, N+1): # 최대 중량을 우선으로 내림차순 정렬

        arr[i].sort(reverse=True)

       

    weight = [0] * (N+1) # 시작점부터 다음 노드까지의 중량

    dijk(start, end)

 

 

섬 3개가 삼각형으로 이루어져 있다고 생각하고, 이것을 반복한다라고 생각하면 편한 것 같다. 그림을 보면 3가지 경우가 있다. 

중량제한 문제에서 최대 힙 추가설명

 

추가적으로, 이분탐색 + BFS를 이용하는 방법이 있는데, 다른 블로그를 참고해보자!