[알고리즘] union find(disjoint set)

[union find]

 

union find는 집합을 트리로 표현한다.

하지만 실제로 그래프를 구현하는 것은 아니고, 배열을 통해 트리를 표현한다.

 

한 개의 트리는 한개의 집합이고, 트리의 구조는 상관이 없다.

각 트리의 대표자가 누구인지, 각 집합을 대표하는 노드가 뉴구인지만 잘 확인해주면 된다.

 

1. Find 연산

하나의 원소가 어떤 집합에 속해있는지를 판단하는 연산

find_parent라는 함수로 구현한다.

자신의 부모를 조회하므로써 자신이 어떠한 집합에 속해있는지 확인한다.

 

2. Union 연산

서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산 
update_parent라는 함수로 구현한다.

A의 부모를 B로 업데이트 한다.

→ A를 B의 집합에 넣는 것이다.

 

---

[find_parent]

int find_parent(int x) {
	if(x==parents[x]) {
    	return x;
    }
    
    return parents[x] = find_parent(parents[x]);
}

find_parent 연산이 수행되면, 재귀적으로 트리를 거슬러 올라가 최상위 노드의 값을 반환한다.

여기서 최상위 노드값이란 해당 집합을 대표하는 노드를 의미한다.
트리 형태로 구현된 disjoint set에서 최상위 노드는 각 집합과 1대1로 대응되므로 findParent 연산을 통해 각 집합을 알 수 있다.

 

[find_parent 최적화 - 경로 압축]

return parents[idx] = find_parent(parents[idx]);

 

find_parent 연산을 수행할때마다 매번 트리를 재귀적으로 거슬러 올라가는 것은 분명 시간낭비이다.
만약 트리의 원소가 편중되어 있다면, 시간복잡도는 O(N)에 근접하게 된다.

편중되어있지는 않지만 Depth가 있는 트리의 예시

편중되어있는 Union Find 트리의 예시

따라서 위와 같은 트리가 나오는 것을 방지하고,

시간복잡도를 줄이기 위해,

findParent 연산에서 방문하는 각 노드마다 결과값을 return 하기 전에 배열에 해당 원소값을 저장한다.

 

답을 찾는 과정에서 트리의 depth를 줄이는 것이다.
이렇게 하면 경로를 압축하는 효과가 있다.

→ 즉, 트리의 depth를 줄이는 과정을 통해 최적화 하는 것이다.

 

 

[update_parent]

void update_parent(int x, int y) {
    x = find_parent(x);
    y = find_parent(y);
	
    if(x!=y) {
    	parents[y] = x;
    }
}

update_parent는 두 노드를 같은 집합으로 만드는 연산이다.

두 개의 집합을 동일한 집합으로 만드는 연산이기도 하다.

A 집합에 있는 1번 노드랑 B 집합에 있는 2번 노드에 대해 update_parent를 수행하는 것을 생각해보면 된다.

 

---

[union find in graph algorithm]

그래프 이론 문제에서 굉장히 많이 쓰인다.

보통 사이클 여부를 판단할때 동일한 사이클인지 파악하기 위해 사용한다.

한 그래프 내부에 포함되어있는지를 판단하기 위해 크루스칼 알고리즘 내부에서도 쓰이는 핵심 알고리즘이다.

공간복잡도와 시간복잡도를 엄청나게 줄이는게 개사기인 부분이고 
각 케이스를 적용한 후에 최적화된 상황을 만들어주는 것도 개사기임.
 
그래프를 표현하는데 1차원 배열만 사용한다는걸 이해해야한다.

---

[union_find의 핵심]

 
여기서 중요한건 트리가 이진트리가 아니여도 된다는 것이다
사실 이걸 트리라고 부르기도 애매하다. 그래프라 부르는게 더 나을까 싶기도 하다

나는 맨 처음에 왼쪽처럼만 하면 백준 통과하겠지 생각하고 왼쪽처럼 짰다.
예제랑 질문게시판 반례 모두 통과했는데 시간초과가 나서 왜일까 하고 보니
이걸 오른쪽처럼 아예 완벽하게 최적화되어있게 만들어야하는 것이었다.
 
그래서 find함수와 union함수를 ㅈㄴ 잘 구현해줘야하는데 
이때 parameter로 들어온 노드의 부모만 최신화시켜주는게 아니라
 
parameter로 들어온 노드의 부모를 찾으면서 통과하는 모든 노드들을 최신화시켜주어야한다
그러면 오른쪽과 같이 된다.

 

---

[union find 알고리즘 과정]

 
여기서 중요한게 위 그림의 오른쪽처럼 "최적화"를 시켜줘야하는건 맞는데
매번 저런 그래프가 나올 수 는 없다는 것이다.
 
예를 들어
그냥 서로 연결되어있지 않은 노드를 편향되지 않게 연결시켜준다면
 
ex) 
1-2
1-3
 

자동으로 최적화된 상태로 나온다. 편향트리가 아닌.
 
근데 만약 저 그래프에 다른 그래프를 다음과 같이 연결시킨다면
 
4-1 연결

노드1과 노드4 모두 부모노드(루트노드)이므로 함수를 거쳐도 서로 1과 4를 반환하고
노드2와 노드3의 부모노드는 업데이트가 안된채 왼쪽그래프와 오른쪽 그래프가 합쳐지게 된다.
다음과 같이 말이다.
 

그럼 이놈은 우리가 원했던 최적화된 상태가 아니다.
 
그럼 얘를 어떻게 최적화 시킬 수 있을까

그건 2,3번이 알고리즘의 주체가 되면 된다.

얘내가 인자로 들어가면 된다는 얘기다.
 
일단 현재 상황은 아래와 같다.
초록색은 각 노드의 배열값 즉 자신의 부모노드 값
 

만약 2-4나 2-5 또는 2-1이 들어간다면
알고리즘은 4 5 1의 부모노드 값인 4를 반환할 것이고
 
이게 bottom-up 방식인 재귀호출에서 return되면서 arr[2] 의 값을 4로 최신화시켜줄 것이다.
이때 최적화가 진행된다.
 
그럼 아래와 같이 우리가 원하는 그림과 가까워진다. 
 

여기서 만약 더이상 3에 대한 연결이 명시되지 않으면
그냥 이게 최선의 그래프인 것이다.
 
완벽하게 최적화된, 즉 모든 노드가 4와 연결된 그래프를 원하면
맨 마지막에 우리가 일부러 각 노드에 함수를 호출시켜주면 되긴 하는데

명시된 연결들로는 위 그림이 최선의 그림인 것이다.

 

[최종적인 경로 압축 진행 = 모든 자식 depth를 1로]

 

여기서 3의 부모노드까지 4를 만들기 위해서는 

모든 데이터를 입력한 후 또 한번의 findParent 함수를 써야한다

그래야 부모노드까지의 depth가 1인 상황이 만들어지기 때문이다.

 

즉, 데이터를 그냥 입력하는 상황에서 사용한 findParent 만으로는

한 집합의 모든 노드가 같은 parent 배열의 값을 갖는다는 것은 보장할 수 없다는 것이다!

 

따라서 무조건 마지막에

한번 더 각 원소에 대해 findParent를 진행시켜야한다!

 

for (int i = 1; i <= N; i++) { find_parent(i); }