🔵 유니온 파인드(Union-Find)란?
다른 말로 disjoint-set구조라고도 한다.
union연산과 find연산 기본적으로 단 2개만을 지원하는 자료구조이며
disjoint한 집합들을 표현하는 자료구조다.
이게 표현하려는 집합들은 어떤 두 집합 사이에도 교집합의 원소가 하나도 없고, 모든 집합의 합집합은 전체집합이라는 말이다! (파티션과 같다고 보면 된대)
이 자료구조는 항상 여러 개의 트리 형태를 띄고 있으며, 그 트리 컴포넌트들 각각이 하나의 집합이다.
예시를 통한 설명
제일 초기의 N=8인 유니온 파인드다. 아무런 연산도 가해지지 않았다.
또한 이게 포함하고 있는 것은 집합도 N개이며 각각 원소 하나를 포함하고있는 형태, 즉 {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}이다.
몇번의 연산이 이루어져 위와 같은 형태가 되었다고 하자.
초기의 상태를 나타내는 포레스트. 각 정점들이 모두 자신이 크기 1인 트리의 루트다.
변형 후 상태를 나타내는 포레스트의 예. 가장 위에 있는 노드가 각 트리의 루트라 본다면 그 트리에 속해있는 정점들은 같은 집합에 속해있다. 같은 집합이더라도 표현할 수 있는 방법은 수없이 많다. 루트가 바뀌어있을 수 있다.
◼ find 연산
두 원소가 같은 집합에 속해 있는지 확인하는 방법은 각각의 루트를 찾아서 둘이 같은지 비교하는 것이다. 그러기 위해서 존재하는 연산이 find연산으로, 어떤 정점의 루트를 찾아준다. 자신이 루트라면 바로 자신을 리턴하면 된다.
int find(int n){
if(p[n] < 0) return n;
return find(p[n]);
}자신의 부모를 가리키는 배열이 p이고, 자신이 루트이면 그 값이 -1이라고 하자. 그러면 자신의 루트를 찾는 find연산은 이렇게 재귀함수로 구현할 수 있다. 물론 맨처음에 배열 전체 값을 -1 등으로 초기화 해두어야만 한다.
그런데!! 만약 여기서 find(6)을 수행한다면, 6부터 2까지의 경로가 일직선이라서 좀 많은 횟수의 재귀함수 호출이 이루어진다.
게다가 find(6) 같이 이렇게 경로가 길 함수를 많이 부르면 그만큼 총 실행시간 합이 엄청 늘어나버린다...
! 그럼 여기서 만약 한 번 6의 루트가 2인 걸 알았다면, 다음 번에 이걸 다시 구할 필요가 없죠? 그럼 이렇게 합세.
이건 메모이제이션과도 비슷한 아이디어인데, 여기서는 트리가 추후 변형될 수도 있기 때문에 이런 일을 해봅시다. 6의 루트가 2인 걸 알았다면, 6을 떼어내서 바로 2의 아래에 이어버리자!
그렇게 하면 2가 나중에 만약 루트가 아니라 다른 누군가의 자식이 되어도, 2부터 따라가서 새 루트를 찾으면 될 일
그 결과 이렇게 되어서 그리 많은 횟수의 함수 호출이 안필요하게 되었당.
int find(int n){
if(p[n] < 0) return n;
p[n] = find(p[n]);
return p[n];
}이렇게 한 줄만 추가해주면 재귀함수로 경로의 모든 노드의 부모를 루트로 재설정한다.
추가 전 최악의 시간복잡도는 O(NM) 이다. 그러나 이렇게 루트를 갱신해버리면 평균이 O(Mlog*N) 이된다! (로그스타라는 함수는 아크만 함수의 역함수로 미칠듯이 느리게 증가함)
저렇게 느리게 증가해서 평소엔 그냥 1~2라고 봐도 좋고, 웬만해서는 거의 선형시간과 동급 취급된다. 즉, O(M)
위의 루트 갱신 테크닉을 경로 압축(path compression) 이라고 부른다.
◼ union 연산
얜 두 집합을 하나로 합쳐준다.
집합을 도로 분할하는 건 굉장히 힘들지만, 보통 합치는 방향만 필요할 때 유용하다.
일단 합칠 두 집합이 같은건지 확인하고 같다면 그냥 종료한다. 이건 단순히 find 값을 비교하면 된다. 다르다면, 둘 중 하나의 루트를 다른 하나의 루트의 자식이 되게 연결시킨다. 이렇게 하면 두 집합은 하나가 된다.
void merge(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
p[b] = a;
}union(3, 7)을 한 결과는
얘가 될수도
얘일수도...
누굴 루트에 넣느냐에 따라 달라지죵. 누굴 루트로 선정할지는 순수히 작성자 맘.
◾ 집합의 크기
유니온 파인드 구조의 기본은 여기까지가 끝이지만 상당히 여러가지의 추가적인 정보를 쑤셔넣을 수 있다. 가장 대표적인 예가 집합의 크기이다.
처음에 루트의 p배열 값을 모두 -1로 초기화 한다면 절대값은 집합의 크기가 되네염.
void merge(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
p[a] += p[b];
p[b] = a;
}따라서 이런 게 가능하다. p[a] += p[b] 부분, 둘 다 루트니까 각자 - (집합 크기) 값을 갖고있는데 이걸 더하면 합집합의 크기가 될 것이고, 그걸 루트가 될 아이에게 넘겨준다. 이걸 더 변형해서 원래 집합 크기가 큰 쪽이 루트가 되도록 조건문을 만들 수도 있당~
💙 스터디 예제
🟡IV 1717 집합의 표현
🟡V 17352 여러분의 다리가 되어 드리겠습니다!
🟡IV 1976 여행 가자
🟡III 16562 친구비
🟡II 4195 친구네트워크
🟡II 10775 공항
🟡I 3197 백조의 호수
● IV 14868 문명
● III 3830 교수님은 기다리지 않는다
🟡IV 12893 적의 적
