상호 배타적 집합(DIsjoint Set)

개념

Union Find 라고 하기도 한다. 트리 구조를 이용한 상호 배타적 집합의 표현

 

팀끼리 합쳐지는 상황.

어떤 팀(팀 1)이 다른 팀(팀 2) 밑으로 들어가는 상황. 두 팀원들의 팀 ID를 같게 만들어야 함. 

보통은 유저 배열을 모두 돌면서 그 유저가 팀1 소속이면 팀 ID를 팀 2로 만들어주는 방법을 생각했을 것이다.

그러나 모든 유저 배열을 순회하는 것은 비효율 적이다. 

이럴  경우 Disjoint Set을 사용하면 좋다.

 

우선 모든 유저의 팀 ID를 자신의 인덱스로 초기화한다.

어떤 유저(1) 가 다른 유저(2)의 밑으로 들어가면 유저 1의 팀 ID를 2로 만든다. 유저 1의 인덱스는 여전히 1이다. 팀 ID만 2가 된 것이다.

이 상태에서 유저 2 팀이 유저 4를 팀원으로 가진 유저 3팀의 밑으로 들어간다. 그럼 유저 2의 팀 ID를 3으로 만든다. 이런 식으로 트리 구조가 만들어진다.

이 상태에서 유저 1, 2, 4의 팀 ID를 조사해 가다 보면 결국 3을 얻는다. 이렇게 자신이 속한 팀을 알 수 있다.

 

그런데 계속 합쳐져서 트리 높이가 높아지고 일직선 형태가 되면 사실상 리스트와 다를 게 없다. 따라서 트리 높이 조절 방법이 필요하다.

 

트리 높이 조절 기법

Union-By-Rank : 높은 트리에 낮은 트리를 합치기

대장을 찾을 때 대장 갱신