프로그래머스 네트워크 문제(DFS)문제를 풀다가 해결 방법이 생각안나 Union-find로 오버킬? 해버렸다

나는 path compression을 사용하면 parent array에 루트 노드가 각각 저장 되는 줄 알고 있었다. 하지만 사실은 아니였고, 마지막에 parent로 각 노드의 루트 노드를 찾는 과정에서 틀려 버렸던거 같다. 알고리즘 단톡방의 어떤 친절하신분이 "실제로 같은 네트워크에 있어도 parent값 자체는 달라질 수 있어요"라는 의문의 말을 꺼내셔서 이해해는데 한참 걸렸다

하지만

그림까지 그려주시며 나를 이해하게 해주려 노력하셨고, 결국 깨닫게 되었다.

위의 그림과 같이 마지막에 UNION(1,3)을 한 후에도 1,2,3은 같은 네트워크에 있음에도 불구하고 3번의 parent는 2번인것을 확인 할 수 있다.

이렇게 만약 그 노드가 어떤 네트워크에 속한지 알고 싶다면 매번 find(int x)를 써서 루트 노드를 확인하는게 확실한 방법이다.