[python3] 백준 1939 풀이 ( 중량제한, MST, 유니온 파인드 )

문제를 읽어보면 생각보다 간단하다. 여러개의 섬으로 이루어진 나라가 존재한다. 그리고 2개의 공장이 각 섬에 하나씩 존재한다. 섬들은 서로 중량제한이 있는 다리로 이루어져있다. 따라서 중량제한을 넘지 않고 다리를 건너서 한공장에서 다른 공장으로 물품을 이송해야한다. 이때 공장A에서 공장B로 갈때 얼마나 많은 물품을 한번의 이동시 옮길 수 있는지 출력해야한다.

여기까지 읽고나면 그래프 문제라는 감이 온다. 그런데 A공장에서 B공장까지 가야하기 때문에 여러개의 경로가 존재한다.문제는 다리개수가 100,000개이기 때문에 완탐으로 푸는 미친짓을 해서는 안된다.

천천히 고민해보자 우선 다리를 건너는 비용은 문제가 되지 않는다. A->B로 가기만 하면되고 이때 건너는 다리의 중량한계의 최솟값이 가장 큰 경로를 찾으면 된다. 그럼 유리한 방법은 중량한계가 가장 큰 다리부터 건넌다고 가정하고 경로를 만들다가 A,B가 이어지는지 확인하면 된다. 그럼 대략적인 시나리오가 나왔고 무슨 알고리즘을 사용해야할지 감이 온다.

1. 중량한계가 가장 큰 다리부터 건넌다고 가정하고 경로를 만들기 (MST의 크루스칼을 최대힙으로 변형)
2. A,B가 연결되어있는지 == 같은 네트워크에 속하는지 (유니온 파인드)

혹시나 MST의 크루스칼기법과 유니온 파인드를 모른다면 아래의 링크를 참조하면 된다.
https://m.blog.naver.com/ndb796/221230994142

18. 크루스칼 알고리즘(Kruskal Algorithm)

https://guccin.tistory.com/110

[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드)

 

그럼 이제 이걸 코드로 만들면 끝이다. 정답비율이 24%로 낮은 편인데 MST알고리즘과 유니온 파인드를 모르면 상당히 헤맬수 있다고 생각된다. 그러나 이 두 알고리즘을 알면 상당히 깔끔하게 풀리는 문제인거 같다.

"""
mst(크루스칼) + 유니온 파인드
"""
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
hq = []
for i in range(M):
    A, B, C = map(int, input().split())
    heapq.heappush(hq, [-C, A, B])  # 최대힙으로 사용
C1, C2 = map(int, input().split())


def union(parent, A, B):
    A = find(parent, A)
    B = find(parent, B)

    if A <= B:
        parent[B] = A
    else:
        parent[A] = B


def find(parent, node):
    if parent[node] == node:
        return node
    parent[node] = find(parent, parent[node])
    return parent[node]


answer = 1000000000
parent = [i for i in range(N+1)]
while hq:
    C, A, B = heapq.heappop(hq)
    C = -C
    union(parent, A, B)
    answer = min(answer, C)
    if find(parent, C1) == find(parent, C2):
        break
print(answer)