[유니온 파인드] union find 경로 압축

1. union find 경로 압축

Union Find에서 Find 를 할 때 루트가 가장 최 상단에 있다면 시간복잡도가 O(N) 이 나올수가 있기 때문에 굉장히 느리다. 

 

이런 문제점을 해결하기 위해서 우리는 경로 압축이라는 방법을 사용할 수 있다. 

 

부모 루트를 계속 연결시키는 것이 아니라 최상단의 노드를 부모로 정하는 것이다. 이렇게 구현하게 되면 트리의 모양은 바뀌지만 우리가 구현하려고 하는 알고리즘에는 전혀 지장을 주지 않는다. 

 

2. Find 함수 수정 

그래서 우리는 Find 함수를 아래와 같이 조금 수정해주려고 한다.

 

int Find(int x) {
 if (x==parent[x]){
  return x; //루트일 경우 루트 노드 return
 }
 else{
   int y=Find (parent[x]);
   parent[x]=y; // 부모 노드를 최상단 루트로 바꾸어줌
   return y;
 }

}

위 사이트에 올라와있는 코드를 그대로 사용했는데 여기에 parent[x]=y 라는 코드가 추가된 것이다. 

 

이렇게 하면 우리는 O(N)이던 연산의 시간을 O(α(N)) 으로 확실히 줄일 수 있다.