[알고리즘] 그래프 문제에 활용되는 유니온 파인드(union-find)

유니온 파인드 union-find는 여러 노드가 있을 때 두 개의 노드를 연결하여 한 개의 집합으로 묶는 유니온 연산과 두 노드가 같은 집합에 있는지 확인하는 파인드 연산으로 구성된 알고리즘이다.

 

 

유니온 파인드의 기본 개념

union 연산

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

find 연산

노드가 속한 집합의 대표 노드를 반환하는 연산

 

 

유니온 파인드 알고리즘의 동작 과정

1. 유니온 파인드 배열 초기화

ex) 6개의 노드

유니온 파인드 (1)

• 일반적으로 1차원 배열을 이용해 표현한다.
• 처음에는 노드가 연결되어 있지 않기 때문에 각 노드가 대표 노드가 된다.

 

2. 유니온 연산 수행

ex) union(1, 4) 및 union(5, 6) 수행

유니온 파인드 (2-1)

• union(1, 4)
  • 1번의 대표 노드(1번)와 4번의 대표 노드(4번)를 연결
  • 1은 대표 노드, 4는 자식 노드로 합집합 연산을 하므로 배열[4]를 1로 업데이트
• 마찬가지로 union(5, 6)의 결과로 배열[6]을 5로 업데이트

ex) union(4, 6) 수행

유니온 파인드 (2-2)

• 4번의 대표 노드인 1번 노드와 6번의 대표 노드인 5번 노드를 연결
  • 배열[5]를 1로 업데이트

 

3. 파인드 연산 수행

• 파인드 연산은 단순히 대표 노드만 찾는 것이 아니라 찾으면서 그래프를 정돈하고 시간복잡도를 향상시키는 역할을 한다.

ex) find(6) 수행

유니온 파인드 (3)

 

1. 대상 노드의 번호(인덱스)와 배열 값이 동일한지 확인 (배열[6] ≠ 6)
2. 동일하지 않으면 배열값에 해당하는 노드로 이동
   • 동일할 때까지 반복(재귀) (6번 → 5번 → 1번)
3. 동일하면 해당 노드가 대표 노드 (1번)
   • 재귀를 돌아 나오면서 거치는 모든 노드의 배열값을 대표 노드로 변경
   • (5번 및 6번의 배열값을 1로 변경)

 

파인드 연산의 기능

• 연산하면서 거치는 노드들이 모두 대표 노드와 바로 연결되는 형태로 변경됨 (경로 압축)
  • 추후 해당 노드들의 find 연산 속도가 O(1)로 단축됨

 

 

유니온 파인드 관련 문제 링크

• 백준 1717번
• 백준 1976번
• 백준 1043번