Union & Find - 이론

알고리즘 Union & Find 알고리즘에 관해서 정리하고자 한다.

알고리즘 이름 그래도 합치고, 찾는 알고리즘이다.

 

대개 이 알고리즘은 노드별 연결이 되어있을때, 사이클이 존재하는가를 찾는데 많이 사용된다.

 

 

 

위 그림처럼 노드와 간선이 존재한다고 했을때, 해당 그래프에서 사이클이 존재하는가 아닌가를 찾아낼 수 있다.

사람의 눈으로 보면 간단하게 1->2->5->1의 사이클이 보이지만 알고리즘으로는 어떻게 알게되는지 알아보자.

 

 

위와같은 과정을 거쳐 최종적으로는 모든 노드의 root는 1에 연결되어있는 결과를 얻을 수 있다.

 

천천히 살펴보면 

1. (1-2)의 경우, 간선으로 연결되어 있어서 2의 root-node값을 1의 root-node로 바꿔준다.

(여기서 1의 root-node로 변경해준 이유는 1과 2를 비교했을때 1이 2보다 작기때문에 더 큰 노드의 root-node를 변경해준다는 약속을 가지고 진행한 것이다.  

( 만약, 나는 두 노드를 비교했을때 더 큰 노드의 root-node값을 작은 노드의 root-node로 변환해주겠다고 해도 상관없다.)

 

2. (2-3) 3은 2와 연결되어있으므로, 2의 root-node로 변경해준다.

( 단, 조심해야 할 것은 위에서는 2의 저장된 root-node값으로 변경해주는게 아니라, 노드를 재귀적으로 따라가

node == root-node일때의 root-node값으로 변경해 줘야 하는 점을 기억하자 )

 

3. (2-4) 4도 2의 root-node로 변경

 

4. (2-5) 5도 2의 root-node로 변경

 

이것이 Union의 끝이다! 

이렇게되면 root-node 행렬은 각 node별 root-node값을 가지게 되는데 이걸 이용해서 Find를 진행할 수 있다.

 

예를들어, 두 노드가 같은 그래프로 묶여있는지를 찾을 수 있는데, 각 노드별 root-node를 비교하여 같으면 같은 그래프에 속한다고 볼 수 있다.

 

또, 사이클이 생기는지 아닌지 알 수 있는데, (a-b) 노드를 연결하고자 할때 이미 root-node가 둘이 같다면,

(a-b) 노드를 연결했을때 사이클이 생긴다고 판단할 수 있다!

 

이처럼 Union 해놓은 root-node 값을 이용해 Find을 진행했을때, 여러 테스크를 수행할 수 있다.

다음에는 코드적으로 한번 살펴보겠다.