백준 1976 : 여행 가자 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def Find(x):

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

    return disjoint[x]

def Union(A,B):

    A=Find(A)
    B=Find(B)

    if A>B:
        disjoint[A]=B
    else:
        disjoint[B]=A

N=int(input())
M=int(input())

disjoint=[0]*(N+1)

for i in range(1,N+1):
    disjoint[i]=i

for i in range(N):

    L=list(map(int,input().split()))

    for j in range(len(L)):
        if L[j]==1:
            Union(i+1,j+1)

check=0
Travel=list(map(int,input().split()))

for i in range(len(Travel)):
    if i==0:
        check=Find(Travel[i])
    else:
        if check!=Find(Travel[i]):
            print("NO")
            exit(0)

print("YES")

📌 어떻게 접근할 것인가?

전형적인 유니온 파인드 문제입니다.
유니온 파인드를 하기 전에 모든 노드들은 자기 번호를 가르키게 하고

i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 에 맞게 $Union$ 을 잘 해주면됩니다.
그리고 마지막에 모든 여행장소의 최상위 노드가 같은지 확인해줍니다.