알고리즘 - Union Find (Disjoint Set Union, DSU)

Union-Find (합집합 찾기)

• 대표적인 그래프 알고리즘

1. 여러 개의 노드가 존재할 때 두 개의 노드를 선택.
2. 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

(출처. https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html)

사진설명

• 노드끼리 연결이 되어 있지 않을 때에는 자신의 노드를 부모 노드로 설정
• 노드끼리 연결되면 연결된 노드 중 보통 작은 숫자를 부모 노드로 설정
• 예를 들어 1 과 2가 연결되어 있으면 두 노드의 부모 노드는 1임.
• 여기서 3이 추가로 2에 연결되면, 처음 3의 부모 노드는 2임.
• 하지만, 재귀함수를 사용하여 2가 연결된 부모 노드를 확인하여 3의 부모 노드가 1로 바뀜. (값 갱신)
• 따라서 Union find가 실행이 되면 연결된 노드끼리 똑같은 부모 노드를 가지게 됨.