백준 1717 집합의 표현 - 파이썬

문제.

풀이.

유니온 파인드의 이해가 필요하다.

유니온 파인드는 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용된다.

유니온 파인드에는 유니온 연산과 파인드 연산이 있다

1) Union -> 서로 다른 두 트리(집합)을 합치는 연산

2) Find -> 루트 노드를 찾는 연산

 

find 연산은 어떤 노드를 인자로 넘겼을 때, 해당 노드의 루트 노드를 반환하며 재귀 호출의 형태로 구현한다.

시간 복잡도 효율을 높이기 위하여 자식 노드들의 값을 모두 루트 노드를 변경하여 경로 압축 최적화를 진행한다.

 

union 연산은 서로 다른 두 트리(집합)을 합친다. 각 트리의 루트 노드를 비교하여 둘 중 작은 루트 노드를 기준으로 합치게 된다.

 

소스코드.