2024. 8. 22. 14:27ㆍAlgorithm
1. Union-find
'Union-find' 는 '합집합-찾기' 자료구조라 말하며, 서로소 부분집합들로 나뉜 원소들에 대한 정보/데이터를 저장하고 조작하는 자료 구조 중 하나이다. 여기서 '서로소 부분집합'은 부분집합끼리 겹치는 요소가 없는 부분집합을 말하는데 즉, 서로간 공통요소가 하나도 없는 상태의 부분집합을 말한다. 'Union-find' 는 'Disjoin-set(서로소 집합)' 또는 'merge-find set(병합-찾기 집합)' 으로 불리기도 한다.
다시 돌아와서 해당 자료구조는 두 가지의 유용한 연산을 제공하는 것이 특징이다. 바로 'find' 와 'union' 인데 각각 아래와 같은 연산을 수행한다.
- find : 어떤 요소가 주어지면 해당 요소가 속한 집합(서로소 집합)을 반환한다. 즉, 요소가 속한 집합을 찾아주는 연산인 것이다. 일반적으로 요소가 속한 집합을 '대표(알리는)' 값을 반환하는데, 이걸 통해 'find' 결과로 특정 집합에 속한 요소인지 확인이 가능한 것이다.
- union : 두개의 집합을 하나로 합치는 연산을 한다. 좀 더 쉽게 말하면 조건을 통해 하나의 집합에 속하는 것이 맞다 판단하는 경우 한 요소를 다른 요소의 집합에 포함시키게 되는 것이다. 물론 반대로 속할 집합이 없다면 해당 요소를 포함하는 새로운 집합을 가지게 하는 것도 가능하다.
개인적으로 '연산' 이라고해서 어떤 공식 같은 느낌이 아니라 서로소 집합을 분류하는 것이 'union' 이고 각 요소에 대한 서로소 집합을 찾아주는 것이 'find' 라고 이해하는 것이 더 쉽게 이해할 수 있었다.
2. 기본 형태
public void union(int element1, int element2) {
서로소 집합을 합치는 과정
}
public int find(int element) {
특정 요소의 대표 서로소 집합을 찾는 과정
return 대표 서로소 집합을 의미하는 값
}
사실 메서드처럼 정해진 것이 두 연산을 제공하는 것외에는 개인의 필요에 따라 구현내용이 전부달라 기본 형태랄 것도 없지만 가장 중요한 두 연산에 대한 설명을 담아 기본 형태로 잡아 보았다.
'union()' 의 경우 위에서 말한 것처럼 두 파라미터가 각각 속한 서로소 집합에 대해서 합치는 기능을 수행하게 된다. 엄밀히 말하면 정말 집합을 합치는 것이 아니라 대표 서로소 집합을 표현하는 특정 값을 변경하는 것이다. 예로 A, B 라는 회사가 있다 A 의 경우 그룹이라 말 할 정도로 큰 대규모 집단이고, B 의 경우 신생이라 독자적, 혹은 다른 그룹에 속한 계열사라고 했을 때, 만약 B 가 A 에 합병되는 경우 B 사를 우리는 A 의 계열사라고 한다. 이와 같이 두 요소의 대표 서로소 집합을 나타내는 값이 다를 때 두 요소를 비교해 한 쪽이 다른 한 쪽에 속한다면 대표 서로소 집합을 나타내는 값을 다른 한 쪽의 값과 같게 바꿀 것이며 만약 속하지 않는다면 그대로 유지하게 되는 것이다.
'find()' 의 경우 파라미터가 속하는 대표 서로소 집합의 값이 무엇인지 확인하고 반환하는 연산을 수행하게 된다. 기능명에 알맞게 대표 서로소 집합에 대한 정보를 '찾아주는' 역할인 것이다.
3. 사용 예시
class Union {
private int[] id;
public Union(int n) {
id = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
}
}
public void union(int u, int v) {
id[find(u)] = find(v);
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}
위와 같은 클래스가 있을 때, 어떻게 흘러가는지 확인해보자. 각 메서드와 변수에 대한 설명은 아래와 같다.
- int[ ] id : 정수형 배열로 각 위치의 요소들이 어떤 대표 서로소 집합에 속하는지를 인덱스 값으로 담는 역할
- Union(int n) : 정수형 값 'n' 을 받아 객체를 생성하는 생성자의 역할, 'id' 의 초기화가 이루어짐
- union(int u, int v) : 두 정수형 값 'u', 'v' 를 받아 'id[u 의 대표 서로소 집합 값]' 에 'v' 의 대표 서로소 집합 값을 저장하며 두 서로소 집합을 합치는 역할
- find(int u) : 특정 정수형 값 'u' 를 받아 'u' 의 대표 서로소 집합 값을 인덱스로 'id' 에 해당 값을 저장하여 반환하는(찾아주는) 역할
물론 위에 든 예시 외에 다른 구현부가 있어야 하겠지만 핵심이 되는 두 연산에 대해 이야기하고 싶어 최근 풀어본 알고리즘 문제의 일부만을 가져왔다. 각 세부 구현에 대한 부분은 핵심 기능을 유지한채로 목적에 따라 달라지게 된다.