백준 9344 : 도로 (Python)

본문 링크

import sys
input=sys.stdin.readline

"""
이 엔지니어는 교통 시스템을 미리 계획하지 않았다.
그는 그저 선호에 따라 한 개의 길을 선택하고,
도로를 건설하는 일을 모든 도시가 연결될 때까지 반복한다.
p-q를 지으면서 가장 짧은 도로망을 만들 수 있으면 YES를 출력한다. 아니면 NO를 출력한다.
"""
def Find(x):

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


for i in range(int(input())):

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

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

    edge=[]

    for j in range(M):
        u,v,k=map(int,input().split())
        edge.append((k,u,v)) #가중치 먼저

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

    for value,A,B in edge:

        x=Find(A)
        y=Find(B)

        if x!=y:
            if (A==P and B==Q) or (A==Q and B==P):
                answer=1
                break
            if x>y:
                disjoint[x]=y
            else:
                disjoint[y]=x


    if answer:
        print("YES")
    else:
        print("NO")

📌 어떻게 접근할 것인가?

처음에 문제가 이해가 되지않았는데 잘 읽어보면 엔지니어가 일단 모든 간선을 연결하려고 한다.

이때 정점을 연결할때 사이클이 생기지 않으면서 $P$ 와 $Q$ 를 연결하는 간선이 있는지 확인해주면 된다.

즉 사이클이 생기지 않는지가 찾아주는것이 핵심이다.