알고리즘 코딩테스트 핵심이론 강의 - 유니온 파인드

https://www.youtube.com/watch?v=klBh4ZglHYo

📌 유니온 파인드

• 여러 노드가 잇을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지 확인하는 find 연산으로 구성

 

◾ union, find 연산

1. union 연산

• 각 노드가 속한 집합을 1개로 합치는 연산

2. find 연산

• 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환

◾ 유니온 파인드 원리

1. 초기화 한다.

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

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산 수행

• 1, 4번 대표 노드를 찾아 연결
• 5, 6번 대표 노드를 찾아 연결

• 4,6번 노드의 대표 노드를 찾아 연결
  → 4번과 6번은 대표 노드가 아니므로 find연산을 이용하여 대표노드 (1,5)를 찾아 연결

◾ find 연산

• find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산
  find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라, 그래프를 정돈하고 시간복잡도를 향상시킴

◾ find 연산 작동원리

1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동
3. 이동 위치의 index 값과 value 값이 같을 때 까지 (대표 노드 찾을때까지) 반복
   → 재귀함수로 구현
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치를 모든 노드값을 루트 노드 값으로 변경

• index 값과 value 값 비교 → A[6] != 6 → 다름
• value 값이 가리키는 index로 이동 후 다시 비교 → A[5] != 5 → 다름
• value 값이 가리키는 index로 이동 후 다시 비교 → A[1] == 1 → 같음

• 1번 노드가 집합의 루트 노드
  → 재귀 함수를 나오면서 그동안 거치 노드의 value 값을 1번 노드의 value 값으로 변경
• 연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경됨.
  → 추수 노드와 관련된 find 연산 속도가 O(1)로 변경되어
  이후 find 연산 진행 시 경로 압축의 효과가 나타난다.
  예를들어 이후 find(4) 연산을 수행 시 한 번의 이동으로 바로 대표 노드를 찾을 수 있다.