[BOJ/Python] 1939_중량제한

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1

3 3
1 2 2
3 1 3
2 3 2
1 3

예제 출력 1

3

---

풀이

 

문제를 요약해보면 다음과 같다.

 

1. N개의 섬이 존재한다. (1~ N 까지의 N개의 노드가 존재한다.)
2. 섬 사이에 다리가 설치되어 있다면 이동할 수 있다. (다리는 간선이다.)
3. 각각의 다리에는 중량제한이 있으며, 중량제한을 초과하는 양의 물품은 다리를 지날 수 없다. (중량제한은 가중치이다.)
4. 이때, 공장이 있는 섬에서 다른 공장이 있는 섬까지 물품을 이동시켜야 한다.
5. 한 번의 이동에서 옮길 수 있는 물품의 중량의 최댓값을 구하는 프로그램을 작성하라.

 

공장이 있는 A섬과 공장이 있는 B섬이 존재한다면, A섬에서 B섬까지 중량제한이 큰 다리들을 거쳐서 이동하면 된다.

그러면 중량제한이 큰 다리들부터 하나씩 연결해 나가면 된다는 것을 알 수 있다.

여기서 A섬과 B섬이 연결되어 있음을 확인하는 방법은 union & find 를 이용하면 된다.

 

1. 따라서, 이 문제는 가중치가 큰 다리들부터 하나씩 연결해나간다. (union&find 를 이용하여 사이클이 생기지 않도록 한다.)
2. 공장이 존재하는 A섬과 B섬이 연결되어 있는 지 확인한다.
3. 연결되었다면, 현재 연결한 다리들 중 가중치가 가장 작은 값을 출력한다. (가중치가 큰 다리들부터 확인을 하기 때문에, 현재 연결된 다리의 가중치가 곧 출력값이 된다.)

코드는 다음과 같다.

 

import sys
sys.setrecursionlimit(int(1e6))
 
def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
        
 
n,m = map(int,sys.stdin.readline().split())
 
parent = [i for i in range(n+1)]
edges = []
for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    edges.append((c,a,b))
 
start,end = map(int,sys.stdin.readline().split())
edges.sort(reverse=True)
 
for c,a,b in edges:
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        if find_parent(parent,start) == find_parent(parent,end):
            print(c)
            break