[Python]유니온파인드 백준 1976

   문제

   https://www.acmicpc.net/problem/1976

유니온 파인드를 한번 사용해보고 다시구현하는 과정에서 합치는과정에 코딩실수로 매

우 고생했다.문제가 쉬워서 실수를 찾기 더욱 힘들었던거 같다.

먼저 이 문제는 DFS나 BFS로도 해결이 가능하지만 경로의 거리에 대한 제한이 없고 

도착만 하면 된다면 루트노드를 확인해서 같은 집합에 있는지만 확인하는 유니온 파인드

를 사용한다면 훨씬 간단하게 구현할수있다.

주의해야할점은 상식적으로는 1->1로 가는 경로는 YES이지만 여기서는 입력에 따라 틀

릴수도있다는 점이다.

import sys
 
def Find(x):#x의 루트노드찾기
    if p[x]<0:
        return x
    else:
        y=Find(p[x])
        p[x]=y
        return y
 
def Union(x,y):
    x_p=Find(x)
    y_p=Find(y)
    if x_p != y_p:#루트노드가 같지 않으면
        p[y_p]=x_p#루트노드를 다른 루트노드에 붙여준다.
 
 
 
N=int(sys.stdin.readline())#도시수
p=[-1]*(N+1)
M=int(sys.stdin.readline())#여행경로 수
# matrix=[[] for _ in range(N+1)]
for i in range(N):
    connection=list(map(int,sys.stdin.readline().split()))
    for j in range(i+1,N):#양방향 연결이기때문에
        if connection[j]:#연결하기
            Union(i+1,j+1)
 
check=True
t_plan=list(map(int,sys.stdin.readline().split()))
tmp=Find(t_plan[0])
for i in range(M):#루트노드가 모두 같은지 확인
    if Find(t_plan[i])!=tmp:
        check=False
        break
 
if check:
    print("YES")
else:
    print("NO")