[ baekjoon ] 군사 이동 11085번 ( python )

문제

백준 11085 군사 이동 풀이 ( 파이썬 )

https://www.acmicpc.net/problem/11085

11085번: 군사 이동

 

풀이

union을 이용했는데 전기가 부족해 등의 문제는 최소값부터 연결해야 했다면 이 문제는 최대 부터 연결하여 연결하다가 Baekjoon World와 Cube World의 부모값이 같아진다면 그 때 연결한 값이 연결된 값중 최소 값이다.

코드를 보면 최대부터 연결하기 위해 최대힙을 이용했다. 파이썬의 기본 heapq는 최소합이기 때문에 -(마이너스)를 붙여 최대힙으로 바꿨다.(꺼낼 때는 원래값을 빼기위해 -를 곱해줘야 함)

import heapq

p,w=map(int,input().split())
c,v=map(int,input().split())

parent=list(range(p))

def find_parent(parent,x):
    if parent[x] !=x:
        return find_parent(parent,parent[x])
    return 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

graph=[]

for i in range(w):
    s,e,width=map(int,input().split())
    heapq.heappush(graph,(-width,s,e))

answer=0

while graph:
    wid,s,e=heapq.heappop(graph)
    wid=-wid
    union_parent(parent,s,e)

    if find_parent(parent,c)==find_parent(parent,v):
        answer=wid
        break

print(answer)