path compression이라는 기법으로, 원래 union-find의 정석 구현법이 맞습니다.

이걸 안 쓰면 시간복잡도가 산으로 갑니다.

무엇이 정석인지는 모르겠습니다만, 수정하는편이 훨씬 효율적입니다.

수정을 하지 않으면 A가 B의 부모, B가 C의 부모, C가 D의 부모.......Y가 Z의 부모 이런식으로 쭉이어진 최악의 경우에

A와 Z가 같은 집합인지 알아보기위해서 Z의 부모의 부모의 부모..........쭉쭉 올라가서 A까지 가게 됩니다.

그러나 저렇게 수정을 해나가는 코드는 C의 부모가 B이고 B의 부모가 A이면 C의 부모를 B가아닌 A로 둡니다.

이런식으로 쭉쭉 수정해나가면 Z의 부모도 A가 되겠고 A와 Z가 같은집합인지 좀더 빠르게 알 수 있죠.

잘못된 비유일수도 있지만 편향트리와 균형트리의 차이점과 비슷하다고 보시면 될것같습니다. 구글에 union find 라고 검색하셔서 그림을 보시며 이해하시면 더 좋을것 같습니다.

답변 감사합니다!

객체지향 프로그래밍 등에서 값을 읽어오는 게터는 내부에서 값을 수정하지 않아야 한다 라는 원칙을 말씀하시는 것 갈은데, 일반적인 ps에서의 코딩과 실무에서의 코딩은 다르다는 점도 염두에 두셔야할 것 같습니다. 어떤 환경에서 어떻게 코딩을 하느냐에 따라 뭐가 좋은 코드냐는 달라질 수 있습니다.

ps에서는 깔끔하고 빠르게 코드를 구현하는게 필요하고 그래서 위와 같은 방식으로 짜는게 제일 정석적인 방법입니다.

네 제가 궁금한게 그거 맞습니다ㅠㅠ 답변 감사합니다!