• 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘
• find 연산: 자신의 대표 노드를 찾아줌

핵심 이론

• union, find 연산을 완벽히 이해하는 것이 핵심

union 연산

• 각 노드가 속한 집합을 1개로 합치는 연산
• 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B를 말함

find 연산

• 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산
• 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표 노드를 반환

유니온 파인드 원리 이해하기

1. 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것입니다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됩니다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화합니다.

1. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행합니다. 배열을 보면 1, 4와 5, 6을 union 연산으로 연결합니다. 배열[4]는 1로, 배열[6]은 5로 업데이트합니다. 1은 대표 노드, 4는 자식 노드로 union 연산을 하므로 배열[4]의 대표 노드를 1로 설정한 것입니다.

• 항상 대표 노드 끼리 연결해준다!!