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

 

유니온 파인드 알고리즘이란?

두 노드에 대해 같은 그래프에 속해 있는지를 파악하는 알고리즘!

 

만약 아래처럼 노드들이 2개의 그래프로 나누어져 있다면 

 

A와 B의 관계에 대해서 어떻게 알아낼 것인가에 대한 알고리즘입니다.

 

 

이름은 생소하지만 어렵지 않은 알고리즘!

 

 

 

구현 방법은 다음과 같이 정리해볼 수 있습니다.

 

 

1. 현재 노드의 부모노드들을 설정

2. 관계에 대해 알고싶은 두 노드들의 최종 부모노드를 비교 /판별 

 

 

이것에 맞게 코드를 구성해 보겠습니다. 

 

 

---

코드!

 

코드는 다음과 같이 간단하게 구성됩니다. 

int parents[51];

...

int Find(int x) { // 최종 부모노드 찾기
	if (parents[x] == x) {
		return x;
	}

	return x = Find(parents[x]);
}

void Union(int x, int y) { //  x의 부모와 y의 부모를 연결
	x = Find(x);
	y = Find(y);
	
	parents[x] = y;
}

 

 

만약 다음과 같이 배열이 주어진다면

A = {1, 4, 7, 8}

B = {2, 6 ,7 ,9}

C = {0, 3, 5}

 

 

0~9까지의 부모를 먼저 설정해 주어야합니다. 초기 부모는 자신으로 지정!

다음은 Union 함수를 통해 연결해 줍시다. 

A를 예로들면 

Union (1,4);
Union (4,7);
Union (7,8);

 

모든 배열을 위와 같이 처리해주면 아래와 같이 연결되는데

 

 

이것을 그래프로 그려보면

이런식으로 표현 할 수 있습니다

 

 

 

이름에 비해 구현은 매우 간단하네요;;

그래프의 구조, 개념정도만 알고 있으면 쉽게 구현 해낼 수 있는 알고리즘이였습니다. 

 

 

 

관련 문제

1043번: 거짓말

 

 

 

 

틀린점이 있다면 댓 달아주세요!