유니온 파인드
- 유니온 파인드
- 유니온: 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산
- 파인드: 두 노드가 같은 집합에 속해 있는지를 확인하는 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차원 배열을 이용하는 것이다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표노드가 된다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화 한다.
- 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다. 배열을 보면 1, 4와 5, 6을 union연산으로 연결한다. 배열[4]는 1로, 배열[6]은 5로 업데이트한다. 1, 4의 연결을 예로 들어 설명하면 1은 대표 노드, 4는 자식 노드로 union연산을 하므로 배열[4]의 대표 노드를 1로 설정한 것이다. 다시 말해 자식 노드로 들어가는 노드값 4를 대표 노드값 1로 변경한 것이다. 그 결과 각각의 집합이었던 1,4는 하나로 합쳐진다.
이제 union(4, 6)으로 4와 6을 연결해본다. 그런데 4, 6은 대표 노드가 아니다. 그래서 각 노드의 대표 노드를 찾아 올라간 다음 그 대표 노드를 연결한다. 지금의 경우 4의 대표 노드 1에 6의 대표 노드 5를 연결한 것이다. 배열은 그럼 [1, 2, 3, 1, 1, 5]가 된다. 배열 상태로 보면 그래프의 연결이 잘 안 보일 수도 있겠지만 다음 find연산 설명을 보면 위 배열이 그래프 연결을 잘 나타내고 있다는 것을 쉽게 이해할 수 있다.
- find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킨다. 이 특징은 매우 중요하다.
📌 find 연산의 작동원리