서로소 집합 알고리즘(2)/ 경로압축기법

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 경로압축기법을 사용한 서로소 집합 알고리즘

 

특정 원소의 루트노드를 찾기 위해 경로 압축 기법을 사용하여 효율적으로 문제를 해결할 수 있다. 이전 방식에서 루트 노드를 구하는 함수에선 부모노드 테이블의 원소가 루트 노드가 아닌 바로 위에 존재하는 부모노드의 루트노드로 설정하였지만 경로압축기법을 사용하면 부모노드 테이블의 원소를 해당 원소의 루트노드로 바로 갱신시켜줄 수 있다. 

 

즉 경로압축기법을 사용하면 이전 포스팅의 예시에서 다뤘던 결과 테이블이 다음과 같은 형태로 바뀐다. 

해당 방법을 사용하면 계속해서 루트노드를 찾기위해 부모노드를 탐색해야하는 과정이 없어지므로 시간복잡도가 개선될 수 있다. 

 

 

▷ 구현

코드는 find_parent함수만 제외하곤 이전 포스팅에 넣은 코드와 동일하다. 

 데이터 입력하고 결과를 출력한다.

이전과 달리 부모테이블의 값이 루트 노드로 바뀌어있음을 알 수 있다.