[🥇4 / 백준 1939 / 파이썬] 중량제한

 

1939번: 중량제한

 

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

 

예제 입력 3 3 1 2 2 3 1 3 2 3 2 1 3

예제 출력 3

 

풀이

 

BFS + 이분탐색, 크루스칼, 프림 등 다양한 방법을 통해 풀이할 수 있는 문제이다.

필자는 프림 알고리즘을 이용하여 해결했다.

원래 프림은 보통 최소 신장 트리를 만들 때 사용하는 것이지만, 이를 적절히 응용하여 해결이 가능했다.

최소 신장 트리 문제라고 하기엔 애매하지만, 알고 있어야 하는 알고리즘이 이렇다보니 해당 카테고리로 분류했다.

 

프림은 다익스트라와 비슷하게 진행된다.

단, 다익스트라는 가중치를 계속 더하며 갱신해나가지만, 프림은 간선의 가중치 그 자체를 힙에 담는다.

 

풀이 방법을 정리하자면 다음과 같다.

 

1. 현재 시점에 힙에 들어있는 가중치가 가장 높은 간선을 뽑아서 진행한다.
2. 방문 정점을 체크하되, 두 정점 사이에 여러 간선이 있을 수 있으므로 boolean 형태가 아닌 int로 기록하여 값을 비교한다.
3. 현재 다리가 버틸 수 있는 최대 무게를 갱신한 뒤, 현재 정점과 연결된 간선을 힙에 추가한다.
4. 위 과정을 반복하다가 도착점까지 도달하게 된다면 그때의 최대 중량을 출력한다.

 

import sys, heapq
input = sys.stdin.readline

INF = -1000000000
n,m = map(int,input().split())
link = [[] for _ in range(n+1)]
visited = [-INF]*(n+1)
for _ in range(m):
    a,b,c = map(int,input().split())
    link[a].append((b,-c))
    link[b].append((a,-c))
start,end = map(int,input().split())

hq = [(INF,start)]
while hq:
    max_w,v = heapq.heappop(hq)
    if v == end:
        print(-max_w)
        break
    for toNode,weight in link[v]:
        if visited[toNode] <= weight:
            continue
        visited[toNode] = weight
        heapq.heappush(hq,(max(max_w,weight), toNode))