[백준] Python - 집합의 표현

1717번: 집합의 표현

DisJoint Set과 Union-Find에 대해 공부하기 위해서 새로 문제를 선택했다.

DisJoint Set은 서로소 집합 또는 분리 집합이라고 한다.

자식이 자신의 부모를 가리키는 형태로 존재하고 집합 간의 교집합은 존재하지 않는다.

 

이 문제의 경우 Union과 Find를 구현하는 기본적인 문제이다.

입력으로 주어진 값에 따라 합집합을 수행할 것인지 값을 찾을 것인지 선택한다.

 

Union의 경우 합치려는 두 대상의 최 상위 부모를 서로 연결한다.

Find의 경우 찾으려는 대상의 부모를 해당 그래프(트리)의 최 상위 부모로 변경한다.

 

Find를 통해 부모가 같은 값들은 하나의 집합으로 묶이게 되는 것이다.

 

한 가지 내 코드에서 부족했던 점은 재귀 호출 횟수 에러가 발생하는 것인데 이 문제를 풀고 나서 다른 사람들의 풀이를 참고하니 

setrecursionlimit 호출 없이도 해결한 사람들이 종종 보였다.

그 코드를 이해하고 좀 더 효율적으로 바꾸는게 필요할 것 같다.

 

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음