[Algorithm] 그래프 유니온 파인드 (Union-Find)

유니온 파인드

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

 

-> 그래프 문제에서 부분 알고리즘으로 많이 사용된다.

유니온 파인드의 원리 

1. 초기화

 

2. union 연산 수행

 

3. find 연산: 자신이 속한 집합의 대표 노드를 찾는 연산

이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다.

• 경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형하여 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.

 

 

 

• 참고 자료
• https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148395