TIL 016 유니온 파인드

📕 유니온 파인드

유니온 파인드, 혹은 분리 집합은 트리 형태의 자료구조이다.
그래프 문제를 풀 때, 순수히 노드간의 연결을 파악할 때 유용하다.
이를 위해 같은 부모노드를 담는 배열을 만들어 같은 부모 배열을 가지는 지 확인한다. (노드의 부모배열이 무조건 부모 배열이라는 보장은 없다. (재귀로 찾아들어가야함)
또한, 시간복잡도를 줄이기 위해 부모노드를 찾는 과정의 중간노드에도 부모노드를 업데이트 해줄 수 있다.

다음 두 개의 함수만 기억해놓으면 간단히 구현가능하다.

def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a] 

def union(a,b):
    global parent

    a = find(a)
    b = find(b)
    if a == b:
        return
    parent[a] = b
    

연습문제)
백준 여행가자

#여행가자
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
parent = [i for i in range(N+1)]

def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a]

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

for i in range(N):
    A = list(map(int,sys.stdin.readline().split()))
    for j in range(N):
        if A[j] and i != j:
            union(i+1,j+1)

A = list(map(int,sys.stdin.readline().split()))
flag = True
for i in range(0,M-1):
    if find(A[i]) != find(A[i+1]):
        flag = False
        break

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