⚠️ 에러

백준 온라인저지 63% 부분에서 시간초과가 발생하였다.

---

👀 원인

유니온 파인드의 경로 압축을 하지 않아 발생

가. 경로 압축이란?

해당 위의 그림처럼 아래의 find 변경시켜 parent 배열을 바꿔 탐색 경로를 줄이는 행위를 말한다.

parent는 상위 루트 노드를 의미

static int Find(int[] parent, int n) {
        if (parent[n] == n) {
            return n;
        }
        return parent[n] = find(parent, parent[n]);
    }

---

👍🏻 해결

위에 코드에서 $find[n] = find$로 받음으로써 실행된다.
이게 무슨 의미냐면 만약 위의 그림같은 경우에 기존의 아래 코드

return  find(parent, parent[n]);

만 한다면 계속 1,2,3의 parent노드를 탐색(parent배열 탐색)하여 최대 O(N)의 시간이 걸릴 수 있다. 따라서 만약 루트 노드를 찾게되면 재귀함수가 스택에서 빠져나오면서 $parent[n]$을 parent값으로 갱신해줘서 위의 그림의 오른쪽 부분과 같이 만들어 준다는 것이다.

즉, 상수시간대로 시간복잡도 단축이 가능하다.