백준 1976 여행 가자 Python

🐸 문제 정보

1976번: 여행 가자

 

🤖 알고리즘

유니온파인드

 

⏱️ 풀이 시간

 failed

 

📝 풀이

너무 오랜만에 유니온 파인드라 결국 예전에 작성해뒀던 아카이브를 찾아봤다ㅠㅠ

예전 벨로그에서 작성했던 유니온 파인드 관련 글이다.

velog

 

유니온 파인드로 각 노드 별 연결 여부를 찾아내면 나머지는 쉽게 풀 수 있었다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = int(input().rstrip()), int(input().rstrip())
parent = [i for i in range(n + 1)]
for i in range(n):
    link = list(map(int, input().rstrip().split()))
    for j in range(n):
        if link[j] == 1:
            union(i + 1, j + 1)

plan = list(map(int, input().rstrip().split()))
start = parent[plan[0]]
for i in range(1, m):
    if start != parent[plan[i]]:
        print('NO')
        exit()
print('YES')