[그래프] 유니온 파인드

✔ 유니온 파인드

유니온 파인드란?

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

union 연산

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

find 연산

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

유니온 파인드 과정

1. 처음에는 노드가 연결되어 있지 않아 각 노드가 대표 노드가 되므로 1차원 배열을 이용하여 배열을 자신의 인덱스값으로 초기화
2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행
   • 예) 1, 4의 연결
   • 1은 대표 노드, 4는 자식 노드로 union 연산을 하므로 
     자식 노드로 들어가는 노드값 4를 대표 노드값 1로 변경하여 각각의 집합이었던 1, 4는 하나로 합쳐짐
   • 이렇게 union 연산을 통해 여러 노드를 합치게 될 경우의 배열 상태를 보면 그래프의 연결이 잘 안 보일수도 있겠지만
     find 연산을 하면 그래프 연결을 쉽게 이해할 수 있음
3. 자신이 속한 집합의 대표 노드를 찾는 find 연산을 수행
   • 대상 노드 배열에 index 값과 value 값이 동일한지 확인
   • 동일하지 않으면 value 값이 가리키는 index 위치로 이동
   • 이동 위치의 index 값과 value 값이 같을 때까지 (대표 노드를 찾을 때까지) 위를 반복
     반복이므로 이 부분은 재귀 함수로 구현
   • 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경
   • 이러한 find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라
     모든 노드가 루트 노드에 직접 연결되는 형태로 변경되도록 하여 그래프를 정돈하여
     이후 find 연산이 진행될 때 경로 압축의 효과가 나타나 시간 복잡도를 향상시킴

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn