1. Union-Find 란?
이는 Disjoint-Set을 표현할 때 사용되는 자료구조이다. Disjoint-Set이란 공통의 원소가 없는 "상호 배타적"인 부분 집합으로 이루어진 원소에 대한 정보 저장 / 조작을 수행하는 자료구조를 의미한다.
자, 여기서 몇 가지 용어를 이해해 보자.
- Set - 집합을 의미한다. 원소를 가지며 순서는 고려하지 않는다.(List와의 차이점)
- Subset - 부분 집합을 의미. 집합 A의 모든 원소가 집합 B에 포함된다면 A를 B의 부분 집합이라고 한다.
- Superset - 초월 집합을 의미. 집합 A의 모든 원소가 집합 B에 포함된다면 B는 A의 초월 집합이라고 한다.
- 상호 배타적 집합 - Mutually Disjoint Set. A와 B가 서로 공유하는 원소가 전혀 없는 경우이다.
- Partition - 분할. 집합 A를 집합 B / 집합 C로 나누어 원소를 쪼개는 것을 의미한다. 이 때, B, C는 상호 배타적이며 A의 모든 원소를 분할해서 갖는다.
왜 Disjoint-Set을 표현하기 위해 Union-Find 자료구조를 사용할까? 그것은 다음과 같은 연산을 수행할 수 있어야 하기 때문이다.
- initialize : 초기화. N개의 원소를 각 집합에 포함되도록 설정.
- union : 합집합 연산. 두 원소 a, b가 있으면 각 원소가 속한 집합을 하나로 합침.
- find : 찾기 연산. 어떠한 원소 a가 주어지면 해당 원소가 속한 집합을 찾아서 반환.
2. 배열로 구현하기
배열로 구현하는 것은 매우 간단하다. 배열을 하나 생성하면 각 Index에는 해당 Index에 해당하는 수가 속한 집합의 번호를 매기는 방식으로 진행될 수 있다.
만약, 숫자가 아니라 객체 형태의 원소라면 속한 집합의 번호를 저장하는 배열과 별도로 객체를 저장하는 배열을 만들어 상호 연동 시키는 등의 추가적인 작업을 수행하면 된다.
숫자로만 이루어진 원소를 갖는 경우를 생각해보자. 초기에 1 ~ 9까지의 숫자가 주어지고, 각각은 자기 자신만 갖는 집합으로 이루어져 있다고 생각해보자.
초기화 연산(initialize)을 통해 아래와 같은 형태의 배열 Array를 만들었다고 가정한다.
| Index i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| num | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
여기서, 1, 2 를 하나의 집합으로 구성하고 싶다고 하자.
합 연산(union)을 통해 수행할 수 있다. 단순히 더 작은 번호로 집합 번호를 고정한다고 해보자. 그러면 단순히 Array[2] 만 방문해서 그 해당 값을 1로 바꾸면 될까? 일단 해보자.
| Index i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| num | 1 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
자, 보다시피, 1, 2는 같은 집합에 속하게 되었다. 이번엔 3, 4를 같은 집합으로 묶어보자. Array[4]만 3으로 바꾸면 되지 않겠는가? 그러면 아래와 같이 될 것이다.
| Index i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| num | 1 | 1 | 3 | 3 | 5 | 6 | 7 | 8 | 9 |
자, 여기까지 너무나 쉽게 진행했다. 이번엔 1, 3을 하나의 집합으로 만들고 싶다고 하자. 이번에도 1이 더 작으니 Array[3]만 1로 바꾸면 될까? 안된다. 3이 있던 집합에는 4도 있기 때문에 4 또한 1의 집합으로 이동시켜야 한다.
여기서 문제가 발생한다. 같은 집합에 속한 원소를 모두 찾아서 바꾸어야 하는데 어떤 원소가 그러한지 알 수 없으니 매 합 연산을 수행할 때마다 전체 원소를 다 탐색해야 한다. 즉, 시간복잡도가 O(N)이 된다. 만약 합 연산을 M회 진행한다면 O(N * M)이 될 것이다.
찾기 연산(find)은 어떨까? 단순히 배열에 위치에 방문해서 값을 가져오면 되므로 O(1)이 소요된다.
그런데 이 Disjoint-Set 문제는 합 연산을 보통 더 많이 수행한다. 그런데 O(N * M)의 시간복잡도로는 절대 효율적으로 문제를 풀 수가 없다. 그래서 단순 배열이 아닌 트리(Tree) 구조를 사용해야 한다.
3. 트리(Tree)로 구현하기
자, 배열로 구현했을 때의 단점을 보완하기 위해 트리 구조를 가져왔다. 어떻게 이를 구현할 수 있을까? 아래의 그림을 한 번 보자.
대충 감이 오는가? 빨간 색은 전체 원소에 대한 집합을 대표하는 노드이다. 그 아래의 자식 노드들은 빨간색인 루트 노드에 대한 포인터를 갖거나 재귀적으로 연결되어 최상위의 루트 노드를 가리키도록 구현되어 있다.
즉, 직접적으로 자신이 속한 집합의 값을 알지 못할 수도 있으나 전체 트리 구조 속에서 하나의 집합으로 구성되어 있는 것이다.
이와 같이 구현된 규칙은 다음과 같다.
① 하나의 트리 구조 내에 모든 원소를 표현한다.
② 전체 트리의 대표 집합은 루트 노드에 원소로 저장된다.
③ 합 연산을 수행 시, 서로 가리키는 루트 노드가 다른 경우에만 합 연산을 수행할 수 있다.
④ 모든 노드는 부모 노드에 대한 포인터를 가지며 종국적으로 루트 노드에 대한 포인터로 이어진다.(재귀적)
이제 이 내용을 코드로 구현해보자.
① 초기화 연산(initialize) 구현
초기화 연산은 기존의 배열로 구현 시와 동일하다. 물론 상황에 따라 요구하는 바가 달라 초기화하는 방법도 달라질 수 있지만 기본적으로 각 집합을 숫자를 원소로 갖고 초기에는 자기 자신을 루트로 인지한다고 가정하자.
여기서는 원소가 1~n 까지 주어진다고 가정하고 구현한다. 코드는 아래와 같다.
package com.test;
public class DisJointSet {
static int parent[];
// ① 초기화 연산 : 1~n 까지의 숫자가 주어진다고 가정하고 초기화
public void initialize(int n){
this.parent = new int[n+1];
for(int i=1; i <= n; i++){
this.parent[i] = n;
}
}
}
② 찾기 연산(find) 구현
찾기 연산은 각 원소가 속한 루트 노드의 번호를 찾는 방식으로 구현한다. 왜냐하면 현재 각 원소가 어느 집합에 속해있는지를 알아내야 하기 때문이다.
각, 원소 배열에는 자신의 부모집합을 가리키는 포인터를 저장하였으므로 재귀적으로 결과를 찾아낼 수 있다. 코드는 아래와 같다.
// ② 찾기 연산 : 각 원소가 어느 집합에 속한지를 확인한다.
// 원소의 번호를 전달하면 그것들 재귀적으로 알아낼 수 있다.
public int find(int e){
// 루트 노드는 자기 자신을 가리키며, 그것이 대표 집합의 번호가 된다.
if(this.parent[e] == e) return e;
// 자신이 가리키는 부모 집합을 찾아간다.
return find(this.parent[e]);
}
③ 합 연산(union) 구현
합 연산은 서로 다른 집합에 있는 원소들을 같은 대표 집합으로 병합하는 연산이다. 예를 들어 원소 e1과 원소 e2의 집합을 합친다고 생각해보자.
어떻게 합칠 수 있을까? 우선 현재 각각의 원소가 속한 집합을 알아야 하니 각 원소의 대표 집합의 번호를 찾아야 한다. 대표 집합을 찾으면 그 대표집합의 번호가 같다면 이미 같은 집합이므로 무시하고, 아니라면 한 쪽의 대표집합 번호를 다른 쪽으로 변경해주면 된다.
일반적으로 더 큰 숫자의 집합을 더 작은 숫자의 집합으로 넣는다.(즉, 대표 집합의 숫자가 더 작은 쪽으로 합친다.)
코드는 아래와 같다.
// ③ 합 연산 : 전달된 두 개의 원소의 대표 집합을 동일하게 만든다.(합친다.)
public void union(int e1, int e2){
// 각 원소의 대표 집합을 찾아낸다.
e1 = find(e1);
e2 = find(e2);
// 같은 집합인 상태라면 불 필요하다.
if(e1 == e2) return;
// 다른 집합이라면 더 작은 쪽으로 한 쪽의 번호를 바꾼다.
if(e1 < e2){
this.parent[e2] = e1;
} else {
this.parent[e1] = e2;
}
}
이제 코드를 한 번 테스트 해보자. 전체 코드는 아래와 같다.
package com.test;
public class DisJointSet {
public static void main(String[] args){
DisJointSet set = new DisJointSet();
set.initialize(10);
set.union(1, 3);
set.union(2, 4);
set.union(5, 6);
set.union(7, 10);
set.union(1, 7);
set.union(2, 6);
StringBuilder sb = new StringBuilder();
sb.append("원소 1과 5는 같은 집합인가 ? ").append(set.find(1) == set.find(5) ? "YES" : "NO").append("\n");
sb.append("원소 1과 10는 같은 집합인가 ? ").append(set.find(1) == set.find(10) ? "YES" : "NO").append("\n");
sb.append("원소 2과 5는 같은 집합인가 ? ").append(set.find(2) == set.find(5) ? "YES" : "NO").append("\n");
sb.append("원소 3과 7는 같은 집합인가 ? ").append(set.find(3) == set.find(7) ? "YES" : "NO").append("\n");
sb.append("원소 3과 10는 같은 집합인가 ? ").append(set.find(3) == set.find(10) ? "YES" : "NO").append("\n");
sb.append("원소 7과 10는 같은 집합인가 ? ").append(set.find(7) == set.find(10) ? "YES" : "NO").append("\n");
System.out.println(sb);
}
static int parent[];
// ① 초기화 연산 : 1~n 까지의 숫자가 주어진다고 가정하고 초기화
public void initialize(int n){
this.parent = new int[n+1];
for(int i=1; i <= n; i++){
this.parent[i] = i;
}
}
// ② 찾기 연산 : 각 원소가 어느 집합에 속한지를 확인한다.
// 원소의 번호를 전달하면 그것들 재귀적으로 알아낼 수 있다.
public int find(int e){
// 루트 노드는 자기 자신을 가리키며, 그것이 대표 집합의 번호가 된다.
if(this.parent[e] == e) return e;
// 자신이 가리키는 부모 집합을 찾아간다.
return find(this.parent[e]);
}
// ③ 합 연산 : 전달된 두 개의 원소의 대표 집합을 동일하게 만든다.(합친다.)
public void union(int e1, int e2){
// 각 원소의 대표 집합을 찾아낸다.
e1 = find(e1);
e2 = find(e2);
// 같은 집합인 상태라면 불 필요하다.
if(e1 == e2) return;
// 다른 집합이라면 더 작은 쪽으로 한 쪽의 번호를 바꾼다.
if(e1 < e2){
this.parent[e2] = e1;
} else {
this.parent[e1] = e2;
}
}
}
위 코드의 결과는 아래와 같다.
원소 1과 5는 같은 집합인가 ? NO
원소 1과 10는 같은 집합인가 ? YES
원소 2과 5는 같은 집합인가 ? YES
원소 3과 7는 같은 집합인가 ? YES
원소 3과 10는 같은 집합인가 ? YES
원소 7과 10는 같은 집합인가 ? YES
4. 최적화하기(Union-By-Rank / 경로압축(Path-Compression))
지금까지 알아본 Union-Find는 하나의 결함을 갖고 있다. 잘 생각해보면 루트 노드를 통해 서로 간에 연결을 시켜 주는 방식이기 때문에 균형 잡힌 트리가 아닌 연결리스트의 형태를 띌 수 있게 된다는 것이다.
5번은 4번 집합에 합치면 5의 집합은 4가 되고, 다시 4를 3에 합치면 4는 3의 집합이 되는데 5는 4의 집합으로 유지된다. 이 과정을 3, 2, 1 순서대로 위 코드처럼 진행하면 단순한 연결리스트 형태가 될 것이다. 이 경우 시간복잡도가 합 / 찾기 연산 모두 O(N)에 달하게 된다.
트리의 구조를 이해했다면 당연히 알 수 있는데, 트리 구조는 높이를 낮출수록 더 빨리 연산이 가능하다. 그를 위해선 균형잡힌 트리를 만드는 것이 중요하다.
여기서 이 경로 압축을 위해 중요한 Key Point는 새로운 집합을 서로 합칠 때, 새 트리를 기존 트리에서 높이가 더 낮은 트리를 높은 트리에 합쳐야 한다는 것이다. 작은 트리가 큰 트리 밑에 가면 높이가 더 변하지 않기 때문이다.
이러한 최적화를 Union-by-Rank라 부르며 rank는 트리의 높이를 의미한다.
rank를 통한 최적화 코드는 다음과 같다.
static int parent[];
static int rank[];
// ① 초기화 연산 : 1~n 까지의 숫자가 주어진다고 가정하고 초기화
public void initialize(int n){
this.parent = new int[n+1];
this.rank = new int[n+1];
for(int i=1; i <= n; i++){
this.parent[i] = i;
// 현재 모든 랭크의 값은 1로 통일. 자기 자신만 존재하기 때문문
this.rank[i] = 1;
}
}
// ② 찾기 연산 : 각 원소가 어느 집합에 속한지를 확인한다.
// 원소의 번호를 전달하면 그것들 재귀적으로 알아낼 수 있다.
public int find(int e){
// 루트 노드는 자기 자신을 가리키며, 그것이 대표 집합의 번호가 된다.
if(this.parent[e] == e) return e;
// 자신이 가리키는 부모 집합을 찾아간다.
return find(this.parent[e]);
}
// ③ 합 연산 : 전달된 두 개의 원소의 대표 집합을 동일하게 만든다.(합친다.)
public void union(int e1, int e2){
// 각 원소의 대표 집합을 찾아낸다.
e1 = find(e1);
e2 = find(e2);
// 같은 집합인 상태라면 불 필요하다.
if(e1 == e2) return;
// 다른 집합이라면 더 작은 쪽으로 한 쪽의 번호를 바꾼다.
if(e1 < e2){
this.parent[e2] = e1;
} else {
this.parent[e1] = e2;
}
}
// ④ 최적화를 위한 union-by-rank 연산
// 트리의 높이를 최소한으로 줄여서 수행
public void unionByRank(int e1, int e2){
e1 = find(e1);
e2 = find(e2);
if(e1 == e2) return;
// 다른 집합이면 더 rank가 작은 쪽으로 붙인다.
// e2가 더 높이가 작다면 e1 밑에 e2를 넣어야 하므로 e2의 값을 바꾼다.
if(rank[e1] > rank[e2]) {
this.parent[e2] = e1;
// e1가 더 높이가 작거나 같다면 e2 밑에 e1를 넣어야 하므로 e1의 값을 바꾼다.
} else {
this.parent[e1] = e2;
}
// 같은 크기의 rank면 union 해서 한 쪽의 아래쪽으로 갔으니 +1을 해줘야 한다.
if(rank[e1] == rank[e2]) ++rank[e1];
}
여기서 변경된 것은 초기화 연산 부분에서 모든 rank를 초기에 1로 채운다는 것과 unionByRank 메소드가 추가되었다는 것이다. 이와 같이 최적화를 한다면 기존의 union 메소드 대신 unionByRank를 사용하면 된다.
여기서 조금 더 최적화를 해서 연산을 더 줄일 수는 없을까? 예를 들어 아래와 같은 그림을 보자.
자 위 그림은 2, 4를 우선 같은 집합에 넣고 3, 5를 같은 집합에 넣고 1, 2, 3를 같은 집합에 넣었다고 볼 수 있는 상황이다.
그런데, 잘 생각해보면 4, 5도 1을 가리키고 있다면 어차피 찾는 것은 루트의 값이므로 연산을 줄일 수 있으니 이득 아닐까? 그렇다. 이를 수행해줄 수 있는 방법이 바로 경로 압축(Path Compression)이다.
경로 압축은 찾기 연산의 특징을 이용한다. 재귀적으로 자신의 부모를 지속적으로 찾아 루트까지 도달하는 방식이기 때문에 찾은 뒤 루트 값이 반환될 때마다 자손들이 가리키는 모든 값을 루트로 차례대로 변환해주는 것이 가능해진다.
일단 코드를 보자.
// ② 찾기 연산 : 각 원소가 어느 집합에 속한지를 확인한다.
// 원소의 번호를 전달하면 그것들 재귀적으로 알아낼 수 있다.
// return 문에 경로 압축 부분이 코딩되어 있다.
public int find(int e){
// 루트 노드는 자기 자신을 가리키며, 그것이 대표 집합의 번호가 된다.
if(this.parent[e] == e) return e;
// 자신이 가리키는 부모 집합을 찾아서 부모를 업데이트 한다.
return this.parent[e] = find(this.parent[e]);
}
이것은 기존의 찾기 연산에서 return 문에 찾은 부모의 루트 집합 번호를 재귀적으로 지속하여 업데이트하는 것을 추가한 것이다. 이를 통해 단계적으로 찾아가지 않고 단번에 루트 집합을 찾게 되는 장점을 갖는다.
위 코드와 같이 수행해서 4번 노드의 찾기 연산을 수행했다고 가정하면 전체 트리 구조는 아래와 같이 바뀐다.
현재는 예시 상 노드가 적어서 그렇지 높이가 기존에 높았다면 연산 속도에 큰 영향이 있을 수 있다.
5. 시간복잡도
Union-Find를 통해 구조화한 Disjoint-Set의 연산 수행 시간은 분석하기가 어렵다. 왜냐하면 경로 압축에 의해 찾기 연산 수행 시마다 전체 수행 시간이 달라질 수 있기 때문이다.(높이 변화)
하지만 대략적으로 경로가 최대 높이일 때, 절반 수준으로 압축될 수 있으므로 이에 따라 계산하면 찾기 연산에 걸리는 시간이 거의 항상 O(4) 수준으로, 이는 거의 선형에 가까운 시간을 유지한다고 한다.
교재에 의하면 평균 수행 시간은 O(a(N))으로 a(N)은 에커만 함수를 통해 정의된 함수로 거의 모든 크기의 N에 대해 4 이하의 값을 가진다고 한다. 거의 상수 시간에 동작하는 수준이며 구현도 간단하고 동작 속도도 매우 빠른 장점이 있다.
참고로 이 Union-Find는 Kruskal's 알고리즘을 위한 핵심적 자료 구조입니다. 해당 내용은 추후에 추가 포스팅을 할 예정입니다.
관련된 백준 알고리즘 문제는 다음과 같다.
1717, 1976, 4195번 문제이며 각각의 링크는 다음과 같다.
6. 참고 - 그래프 Cycle 찾기
Union-find 알고리즘을 이용하여 그래프 형태의 자료구조에서 Cycle이 있는 지를 확인할 수 있다. 그래프 자료구조의 설명은 여기를 참조.
아래와 같은 그림으로 Cycle이 형성되어 있는 그래프 형태가 있다고 가정하자.
위의 그림에서 0 - 1 - 2의 구조로 Cycle(순환)이 형성되어 있음을 알 수 있다. 이것을 Graph로 구현하여 Union-Find 알고리즘을 이용하여 Cycle이 있는지 확인해보자.
방법은 다음과 같다.
① 각 정점을 연결하는 간선 정보를 별도로 저장한 뒤, Cycle을 찾는 함수를 호출한다.
② 함수 내에서 각 정점이 속한 subset을 최초에는 -1로 초기화한다.
③ 간선 정보를 하나씩 꺼내서 두 연결된 정점이 어느 subset에 속하는지를 찾는다.
④ 두 정점이 탐색 기준 현재 같은 subset이라면 다른 경로에 의해 같은 subset에 속하게 되었으니 Cycle이 있는 것이다.
⑤ 다른 subset이라면 두 정점이 연결되었음을 표시하기 위해 같은 subset으로 설정한다.
⑥ 모든 간선 정보에 대해 ③ ~ ⑤를 반복한다.
아래의 코드는 Union-Find 알고리즘을 통해 그래프 내 Cycle을 찾는 것을 구현한 코드이다.
package com.test;
public class DetectCycle {
public static void main (String[] args){
/* 그래프를 아래와 같이 생성
0
| \
| \
1---2 */
Graph g = new Graph(3, 3);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
if (isCycle(g)){
System.out.println("Cycle Detected!");
} else {
System.out.println("No Cycle Detected!");
}
}
// Union-Find의 찾기 연산을 수행하는 메소드
// parent는 어느 그룹에 속하는지 저장되어 있는 배열, v는 현재 정점
public static int find(int parent[], int v){
// -1이라면 가장 최정상에 있는 정점이므로 바로 반환
if (parent[v] == -1)
return v;
// 재귀를 통해 상위 그룹을 찾아간다.
return find(parent, parent[v]);
}
// Union-Find의 합 연산을 수행하는 메소드
public static void union(int parent[], int u, int v){
// 그룹의 합연산 수행
parent[u] = v;
}
// Cycle이 있는지 확인하는 메소드
public static boolean isCycle(Graph g){
// subset을 생성하는 배열을 말들고 초기화(초기에는 -1로 모두 저장)
int[] parent = new int[g.v];
for (int i=0; i < g.v; i++){
parent[i]=-1;
}
// Iterate through all edges of graph, find subset of both
// vertices of every edge, if both subsets are same, then
// there is cycle in graph.
for (int i = 0; i < g.e; i++){
int x = find(parent, g.edge[i].src);
int y = find(parent, g.edge[i].dest);
if (x == y){
return true;
}
union(parent, x, y);
}
return false;
}
// 그래프 생성하는 내부 static class
static class Graph{
// 정점, 간선, 간선 연결 정보 배열
int v;
int e;
Edge edge[];
public Graph(int v, int e){
this.v = v;
this.e = e;
edge = new Edge[this.e];
for(int i=0; i < e; i++){
edge[i] = new Edge();
}
}
// 양방향 그래프 적용
public void addEdge(int s, int d){
this.edge[s].src = s;
this.edge[s].dest = d;
}
}
// 간선 정보를 보유한 클래스
static class Edge{
int src, dest;
}
}
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 알고리즘(Algorithm)' 카테고리의 다른 글
| 알고리즘 - 그래프 탐색(너비 우선 탐색 - BFS) (0) | 2020.12.06 |
|---|---|
| 알고리즘 - 탐색(선형, 이진, 점프, 보간, 삼진 탐색) (2) | 2020.12.03 |
| 알고리즘 - 소수 구하기 (2) | 2020.11.20 |
| 알고리즘 - 최대공약수 / 최소공배수 (0) | 2020.11.19 |
| 알고리즘 - 표기식(전위 / 중위 / 후위) (0) | 2020.11.18 |
