path compression이라는 기법으로, 원래 union-find의 정석 구현법이 맞습니다.
이걸 안 쓰면 시간복잡도가 산으로 갑니다.
1717번 - 집합의 표현
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 라고 검색하셔서 그림을 보시며 이해하시면 더 좋을것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
rktkek456 4년 전
인터넷에서 검색해보면 find에서 재귀함수로 값을 수정하는데
class에서 접근자, 설정자로 변수를 수정 할 수 있는 함수를 제한 하는 것 처럼
find에서는 값을 수정 못하게 제한해야하는거 아닌가요?
원래 find 함수 내부에서 값을 수정하는게 정석적인 구현 방법인지 궁금합니다.