[BOJ/Python] 11085_군사 이동

문제 출처:https://www.acmicpc.net/problem/11085

11085번: 군사 이동

문제

전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 이에 비례하는 수의 군사가 지나갈 수 있습니다.

Baekjoon World의 국왕은 군사들이 뭉치는 것이 유리하다고 생각해서, 미리 Cube World로 가는 경로를 정해 두고 그 경로로만 모든 군사를 보냈습니다. Baekjoon World의 국왕은 총명해서, 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택했습니다.

그런데 전쟁 때문에 어느 길로 보냈는지에 대한 기록이 불타 없어져 버렸습니다. 전쟁사를 완성하려면 이 기록이 꼭 필요합니다. 위대한 과학자인 당신이 다시 복구해 주세요.

입력

첫 줄에 p와 w가 공백을 사이에 두고 주어집니다. (2 ≤ p ≤ 1 000; 1 ≤ w ≤ 50 000)

다음 줄에 Baekjoon World의 수도 c와 Cube World의 수도 v가 공백을 사이에 두고 주어집니다. (0 ≤ c, v < p; c ≠ v)

다음 w줄에 길이 연결하는 두 지점 Wstart, Wend,와 길의 너비 Wwidth가 공백을 사이에 두고 주어집니다. (0 ≤ Wstart, Wend < p; Wstart ≠ Wend; 1 ≤ Wwidth ≤ 1 000)

출력

첫 줄에 Baekjoon World의 국왕이 정한 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 출력합니다.

예제 입력 1

7 11
3 5
0 1 15
0 2 23
1 2 16
1 3 27
2 4 3
2 6 21
3 4 14
3 5 10
4 5 50
4 6 9
5 6 42

예제 출력 1

16

---

풀이

 

문제에 대한 풀이는 다음과 같다.

1. 0부터 p-1 까지 총 p 개의 지점과, w개의 길이 존재한다.
2. c지점과 v 지점이 연결되어야 한다.
3. 이때, 가장 좁은길의 너비가 최대화하는 경로를 선택해야 한다.
4. 여기서, 가장 좁은길의 너비가 최대화가 된다는 조건을 만족하기 위해서는 각 지점을 연결하기 위해 너비가 큰 길들부터 우선적으로 연결시켜야 한다.
5. 따라서, 너비가 큰 길들부터 차례로 연결시키며, 만약 c지점과 v지점이 연결된다면 현재 연결한 길의 너비가 지금까지 연결된 길들의 너비 중 제일 작으므로, 이 값을 출력한다.

 

코드는 다음과 같다.

 

import sys
 
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
 
 
p,w = map(int,sys.stdin.readline().split())
c,v = map(int,sys.stdin.readline().split())
 
parent = [i for i in range(p+1)]
edges = []
for _ in range(w):
    start,end,width = map(int,sys.stdin.readline().split())
    edges.append((width,start,end))
 
edges.sort(reverse=True)
 
for w,s,e in edges:
    if find_parent(parent,s) != find_parent(parent,e):
        union_parent(parent,s,e)
        if find_parent(parent,c) == find_parent(parent,v):
            print(w)
            break