백준 1976 - 여행 가자 (파이썬)

이번 문제는 union-find 알고리즘으로 해결할 수 있습니다. tmp 리스트를 받는 부분을 보시면 1이면 연결 되어 있다는 뜻이므로 union함수를 호출해 주시면 됩니다.

import sys

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

n = int(input())
m = int(input())
parent = [i for i in range(n + 1)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
        
    return parent[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
        
    if x > y:
        parent[y] = x
    elif x < y:
        parent[x] = y
    else:
        return

for i in range(1, n + 1):
    tmp = list(map(int, input().split()))
    for j in range(1, len(tmp) + 1):
        if tmp[j - 1] == 1:
            union(i, j)
            
plan = list(map(int, input().split()))
answer = []

for i in plan:
    answer.append(find(i))
    
if len(set(answer)) == 1:
    print('YES')
else:
    print('NO')