[알고리즘] Union Find 알고리즘 (경로 압축)

기존에도 Union Find 알고리즘을 사용하기는 했지만, 경로 압축을 하고있지 않아 시간이 조금더 걸리는 문제가 있었다. 간단하게 경로압축을 할 수 있는 방법을 배워 글을 써본다. Union & Find 기본적인 Union Find 알고리즘의 구성은 다음과 같다. 맨 처음 parent 배열에서 각각은 자기 자신의 번호를 갖고 시작한다. 다음 숫자들이 Union 연산을 순서대로 진행한다고 해보자. 1 2 가 Union 연산을 진행한다. Union(1, 2) 2 3 3 4 4 5 6 7 7 8 8 9 이 상황을 Tree 로 묘사하면 다음과 같다. 5번과 9번 자기 자신을 root로 하는 tree가 2개 생겼다. 1번 원소를 보면 2번 원소를 화살표로 가리키고있다. 이는 배열에서 1번 칸에 숫자 2가 담..........

원문링크 : [알고리즘] Union Find 알고리즘 (경로 압축)