[중량제한/G3/Python3]

1939번 중량제한 G3

 

문제
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인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력
첫째 줄에 답을 출력한다.

 

 

자료 구조, 그래프 이론, 그래프 탐색, 이분 탐색, 너비 우선 탐색, 분리 집합

 

그래프에서 두 공장을 오갈 수 있는 경로의 최대 중량을 구하는 문제로 요약할 수 있다.

그래프 탐색 알고리즘이 많은 만큼 다양한 풀이 방법이 존재한다.

우선순위 큐를 사용한 다익스트라 풀이 방법과 분리집합을 이용한 크루스칼 풀이 방법을 준비했다.

 

import sys
import heapq

n, m = map(int, sys.stdin.readline().split())

routes = [[] for _ in range(n+1)]
visit = [False] * (n+1)

for _ in range(m):
    v1, v2, c = map(int, sys.stdin.readline().split())
    routes[v1].append((-c, v2))
    routes[v2].append((-c, v1))

s, e = map(int, sys.stdin.readline().split())

hq = []
for c, v in routes[s]:
    heapq.heappush(hq, (c, v))

while hq:
    c, v = heapq.heappop(hq)
    if visit[v]: continue
    visit[v] = True
    if v == e:
        print(-c)
        break
    
    for c2, vv in routes[v]:
        if visit[vv]: continue
        heapq.heappush(hq, (max(c, c2), vv))

최대 우선순위 큐 구현을 위해 음수로 변환된 중량 제한을 넣었다.

다익스트라 알고리즘에 의해 우선순위 큐에서 꺼냈을 때 해당 정점까지 최대 중량 제한임을 보장해 준다.

항상 두 섬이 연결된 입력만 주어지는 입력 조건을 이용해, 우선순위 큐에서 꺼낸 정점이 도착지점이라면, 해당 정점이 가진 중량 제한은 두 섬을 잇는 최대 중량 제한이 된다.

 

 

 

import sys

n, m = map(int, sys.stdin.readline().split())

p = [i for i in range(n+1)]
def find(v):
    if v == p[v]: return v
    p[v] = find(p[v])
    return p[v]

def union(v1, v2):
    r1, r2 = find(v1), find(v2)
    p[r1] = r2

lines = []
for _ in range(m):
    v1, v2, c = map(int, sys.stdin.readline().split())
    lines.append([c, v1, v2])
lines.sort()
s, e = map(int, sys.stdin.readline().split())

while True:
    c, v1, v2 = lines.pop()
    if find(v1) == find(v2): continue
    union(v1,v2)
    if find(s) == find(e):
        print(c)
        break

다리는 서로 오갈 수 있는 양방향 길임을 이용했다.

 

크루스칼 알고리즘의 경우 최소 신장 트리에서 사용되는 알고리즘으로, 모든 정점을 잇는 최소 비용을 구할 때 사용한다.

사이클이 생기지 않는 간선 중 비용이 가장 적은 간선부터 선택해서 연결을 진행하는 탐욕적인 방법이다.

 

위 코드는 해당 논리를 가장 큰 비용부터 선택함으로써 반대로 사용하였다.

Union Find 분리 집합을 이용하면 이미 연결된 상태인지 확인이 가능하다.

 

위 코드의 작동 원리는 다음과 같다.

1. 남아있는 간선 중 중량 제한이 가장 높은 간선부터 연결을 진행한다.

2. 만일 두 섬이 연결된다면 이때 연결된 간선의 중량 제한이 두 섬을 잇는 최대 중량이다.

 

---

 

 

특정 알고리즘 만으로 풀리는 문제가 아닌, 다양한 방법으로 풀리는 문제여서 정이 가는 문제이다.