백준 13905 : 세부 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

N,M=map(int,input().split())

S,E=map(int,input().split())

disjoint=[ _ for _ in range(N+1) ]

edge=[]

for i in range(M):

    a,b,c=map(int,input().split())

    edge.append((c,a,b))

edge.sort(key=lambda x:-x[0])

check=[]
for value,x,y in edge:


    x=Find(x)
    y=Find(y)


    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x

    if Find(S)==Find(E):
        check.append(value)

if check:
    print(max(check))
else:
    print(0)

📌 어떻게 접근할 것인가?

최소 스패닝 트리 알고리즘인 크루스칼을 통해 풀었습니다.

그냥 크루스칼을 구현하지만 , 가중치가 최대가 되어야 하므로 오름차순이 아니라 내림차순으로 정렬해줍시다.

그리고 if Find(S)==Find(E) 즉 , $S$ 에서 $E$ 로 가는 간선이 생기면 그때의 value 값을 저장합니다.

처음에는 변수 하나만 만들고 조건을 만족하면 check=min(check,value) 만 사용하였는데 이렇게 하면 다른경로에서의 최대값을 찾지 못할수 있기 때문에 모든 $S$ 에서 $E$ 로 가능한 경로에 대해 탐색했습니다.

마지막에 저장한 value 값중 최대값을 출력합니다.

이때 없을수도있으므로 없다면 $0$ 을 출력합니다.