알고리즘

🔍 유니온 파인드

이채림 2024. 11. 9. 16:03

📖 유니온 파인드(union-find)

여러 노드가 있을 때 특정 2개의 노드를 연결해

1개의 집합으로 묶는 union 연산

두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로

구성되어 있는 알고리즘

 

 


 

유니온 파인드 알고리즘 구현 방법

 

  • 1차원 배열 이용
    • 대표 노드 저장 배열 초기화
      • 초기에는 노드가 연결되어 있지 않으므로 자신의 인덱스 값으로 초기화
  • 2개의 노드를 선택해 union 연산 수행

⭐️ 항상 대표 노드끼리 연결해준다 ➡️ find 연산 수행

 


 

🧩 find 연산의 작동 원리

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

 

find 연산은 시간 복잡도가 줄어드는 효과를 얻는다.
연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경되고
추후 노드와 관련된 find 연산 속도가 O(1)로 변경된다.

경로 압축의 효과

 

'알고리즘' 카테고리의 다른 글

🔍 그래프와 그래프 알고리즘 정리  (2) 2024.11.08
Java Comparator: 커스텀 정렬 기준  (0) 2024.10.30