유니온-파인드 알고리즘

유니온-파인드(Union-Find) 알고리즘

· 그래프 알고리즘 중 하나로 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

· 상호 배타적 집합(Disjoint-set)

 

 - Union : x와 y가 포함되어 있는 집합을 합치는 연산

 - Find : x가 어떤 집합에 포함되어 있는지 찾는 연산

 

i : 노드번호   P[i] : 부모 노드 번호

위와 같이, 모든 값이 단일 노드일 때 P[i]의 값은 자기 자신이 된다.

 

위와 같이, 1-2, 3-4처럼 연결 관계를 가진다면 부모를 합치는 과정을 수행한다.

부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합친다.  →  합침(Union) 과정

 

 

위와 같은 과정을 거치면 2의 부모 노드에는 1이 3의 부모 노드에는 2가 들어간다.

여기서 1과 3의 연결성을 파악하기 위해 재귀함수가 사용된다.

3의 부모인 2를 먼저 찾고, 2의 부모인 1을 찾아, 3의 부모가 1이 되는 것을 파악한다.

최종적으로 Union 연산을 수행하면 아래와 같은 결과가 나온다.

 

 

 

· Union-Find 알고리즘 관련 문제

 - 백준 1976번 : https://www.acmicpc.net/problem/1976

 - Code(Python)

import sys
input = sys.stdin.readline


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


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


# 유니온 파인드
n = int(input())
m = int(input())
parents = [i for i in range(n)]
for i in range(n):
    link = list(map(int, input().split()))
    for j in range(n):
        if link[j] == 1:
            union(i, j)

# 경로 체크
parents = [0] + parents
path = list(map(int, input().split()))
start = parents[path[0]]
for i in range(1, m):
    if parents[path[i]] != start:
        print("NO")
        break
else:
    print("YES")