유니온 파인드

 

유니온 파인드 알고리즘은 두 노드가 하나의 집합에 속하는지 판별하고 싶을때 매우 유용하게 사용되는 방법이다. 

• 노드를 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.

 

 

 

이렇게 복잡한 그래프에서는 빠른 시간 안에 두 노드가 연결되어 있는지 판별하는 게 힘들다.

바로 이런 경우에 두 노드가 연결되어 있는지, 끊어져 있는지를 판별하는 방법이  "유니온 파인드" 이다. 

 

두 노드가 연결되어있는지 판단하는 방법은 ,  두 노드가 하나의 집합 안에 포함되는지 확인하면 된다. 

그렇게 하기 위해서는 먼저 연결되어있는 노드들을  하나의 집합으로 만드는 과정이 필요하다.  바로 이 과정이 Union (유니온) 이다.

 

예를들어, 1호선이 지나가는 역들은 모두 남색선으로 표시하였다. 이것이 바로 유니온 과정이다.

그럼 어떤 임의의 역의 색깔이 남색인지 아닌지에 따라 1호선에 속하는 역인지 아닌지를 판단할 수 있는 것이다. 

 

---

 

 

아래와 같이 아직 연결관계가 설정되어있지 않은 노드들이 있다고 하자. 

 

처음에는 노드들이 모두 연결관계를 가지고 있지 않기 때문에 각 노드가 대표노드 가 된다. 

 

대표노드란 특정 노드 집합을 대표하는 노드 값으로, 하나의 집합에 포함되어있음을 나타내기 위해  하나의 대표값이 필요하다.

그때 사용하는 노드의 값을 대표 노드라고 하는 것이다. 

 

현재 각 노드는 모두 자기자신의 집합을 대표하는 노드이므로, 배열의 값을 index값으로 초기화해준다. 

여기서 배열의 값은 자신이 속한 집합의 대표노드 값을 의미한다. 

 

따라서 현재는 배열의 인덱스와 배열의 값이 모두 일치한다. 

이미지 출처: Do it 코딩테스트 자바편

 

 

 

이제  1과4 , 5와6 노드를 하나의 집합으로 만들어보자

 

(1,4)   →  대표값 1

(5,6)   →  대표값 5 

 

이렇게 두 노드가 합쳐져 하나의 그래프가 될 때, 자식이 되는 노드의 값에 부모 노드의 값을 적어준다. 

따라서 (1,4)의 노드 집합에서는 부모가 1이므로 A[4]=1로 나타낸다. 

 

 

A[4]=1 , A[6]=5 

 

이렇게 값을 바꾼후 배열의 값을 읽어보자.  4의 부모는 1이고, 6의 부모는 5임이 한눈에 파악된다. 

 

 

이미지 출처: Do it 코딩테스트 자바편

 

 

 

현재의 상황은 아래의 그림과 같다. 

 

이제 노드4와 노드6을 연결해보자. 

 

두 노드의 대표노드 값은 서로 다르기 때문에, 서로 다른 집합에 속하는 노드 인것을 알 수 있다. 

특정 노드의 대표노드 값을 찾는 방법은 아래와 같다. 

 

 

🐟 대표노드 값을 찾는 방법 

• 대상 노드 배열의 index값과 value값이 동일한지 확인한다
• 동일하지 않으면 value값이 가리키는 index로 이동한다
• 이동위치의 index값과 value값이 동일해질때까지 1~2번 과정을 반복한다 (반복이므로 재귀함수로 구현)

 

그리고 이렇게 자신이 속한 집합의 대표노드를 찾는 연산을 find연산 이라고 한다. 

 

 

- 4번 노드의 대표노드를 찾는 방법 

1. 배열의 4번에 있는 값을 확인한다. 1번이다.
2. 배열의 1번에 있는 값을 확인한다. 1번이다.
3. 배열의 인덱스와 값이 일치한다.  

 

 

- 6번의 대표 노드를 찾는 방법 

1. 배열의 6번에 있는 값을 확인한다. 5번이다.
2. 배열의 5번에 있는 값을 확인한다. 5번이다.
3. 배열의 인덱스와 값이 일치한다. 

 

 

4의 대표노드값은 1이고, 6의 대표노드 값은 5이다. 

 

 

 

따라서, 대표노드끼리 연결해주면 된다. 

 

(1,5)   →  대표값 1 

 

노드 5의 부모를 노드1로  설정하기 위해 A[5]=1로 바꿔주자.

그럼 배열의 값은 [1,2,3,1,1,5] 가 된다. 

 

 1의 값을 가지고 있는 1,4,5는 같은 집합에 속하는 것이 한눈에 보인다. 하지만  노드6은 대표노드가 아닌, 인접한 부모 노드인 5의 값을 가지고 있기 때문에 1로 대표되는 집합에 속하는지 한눈에 파악하기 어렵다. 

 

 

 

그렇다면, 대표노드가 1인 집합에 속하는 모든 노드의 값을 1로 나타내면,  해당 노드들이 모두 같은 집합에 속한다는 것을 더 잘 파악 할 수 있지 않을까?  

 

 

🐟 find 연산의 작동원리

• 대상 노드 배열의 index값과 value값이 동일한지 확인한다
• 동일하지 않으면 value값이 가리키는 index로 이동한다
• 이동위치의 index값과 value값이 동일해질때까지 1~2번 과정을 반복한다 (반복이므로 재귀함수로 구현)
• 대표노드를 찾고 재귀 함수를 빠져나오면서 거치는 모든 노드의 값을 대표노드 값으로 바꿔줌 (경로 압축)

 

즉  6에서 find 연산을 수행할때 6 5 1 순으로 재귀함수를 호출했다가, 빠져나오면서  A[6]=1 로 만들어주면 된다. 

 

 

 

 

이렇게 한번의 find 연산으로 모든 노드가 대표노드와 직접적으로 연결되는 형태 로 변형 될 수 있다. 

 

이 방법을 통해, 자식 노드가 아무리 많아지더라도 자식노드에서는  대표노드의 값을 바로 구할 수 있게 된다. 

 

 

 

 

 

 

 

 

🐸 참고 

설명이 매우 잘되어있어서 한번씩 가서 읽어보면 좋을것 같다!! 

[알고리즘] 유니온 파인드 (Union-Find)

 

 

🍥 출처 

서울 지하철 노선도 이미지 : https://www.sisul.or.kr/open_content/skydome/introduce/pop_subway.jsp

그래프 이미지: https://lgphone.tistory.com/90

그 외 이미지: Do it 코딩테스트 자바편