<알고리즘> Union Find

youtu.be/0jNmHPfA_yE

너무 오래전 배웠던 개념이라 일단 다시 찾아서 이해하는데 시간이 걸렸다

 

 

parent의 index는 자식 노드이다.

panret[index] 부모노드이다. 

#define MAX_SIZE 5
int parent[MAX_SIZE+1];

 그렇다면 간단하게 

숫자 1~5라고 가정하자 

이 다섯 노드를 parnet 배열로 표현하면 parent[5]; 가 될것이다.

필자는 #define MAX_SIZE 5 일단 메크로로 만들어 두었다.

 

배열은 처음이 0으로 시작하기 때문에 

1부터 값을 입력해줄것이다.

 

그렇다면 아래의 메인 함수의 for문을 먼저 확인해보자

void main()
{
	for (int i = 1; i < MAX_SIZE+1; i++)
		parent[i] = i;


	Union(2, 3);
	Union(2, 4);
	Union(1, 5);

	for (int i = 1; i < 6; i++){
		cout << parent[i]<<","<<i;
		cout << endl;
	}

}

 

이상태에서 배열에 index에 맞게 i값이 입력된다.

for (int i = 1; i < MAX_SIZE+1; i++)
		parent[i] = i;

위의 그림처럼 될것이다.  *0번 index와 value는 무시하도록하자 여기선 사용하지 않을것이다.

 

우리는 2를 최상단 부모라고 가정을 하고 아래의 그림과 같은 그래프의 형태를 만드려한다.

데이터를 이어서 트리를 만들어 줄것이다. 

 

 

 

Union(2, 3);
Union(2, 4);
Union(2, 1);
Union(4, 5);
Union(5, 3);

그렇다면이 노드들의 관계를   union 함수에 입력을 해줍니다. 

즉 앞에 있는 숫자가 (부모,자식) 노드의 형태를 취합니다. 

마지막 출력은 자식노드들의 가장 높은 부모노드(root)가 누구인지 출력을 할 예정입니다.

 

 

Union 함수입니다.

먼저 부모노드가 find 함수에 input 됩니다. 

그다음 자식 노드가 find함수에 input됩니다. 

그리고  parent[y](자식노드) 에 부모노드(root)가 누구인지 입력해줍니다.  

void Union(int x, int y) {
	
	x = find(x);
	y = find(y);
	
	parent[y] = x;

}

이번에 find 함수를 보겠습니다.

맨처음 부모노드index와 value 값이 같으면 그대로 return 합니다.

ex) parent[2]==2 -> return 2;

다음 만약 다르다면 find() 재귀함수를 통해 현재 value값을 입력해줘서 재귀를합니다. 

int find(int x) {
	if (parent[x] == x) {
		
		return x;
	}
	else {
		return find(parent[x]);
	}


}

이해를 위해 숫자와 그림으로 표현해보겠습니다.

Union(2, 3);
Union(2, 4);
Union(2, 1);
Union(4, 5);
Union(5, 3);

이런식으로 반복될것이다. 그다음 Union(2, 1); 도 마찬가지 같은 방식이다 

그다음 조금 다른 Union(4, 5);  어떻게 흘러가는지 확인해보자 

이와같이 Find가 index와 value가 다르므로 index와 value가 같아질때까지 Find를 재귀를 합니다. 그리고 최종 root에 도달하면 재귀가 끝나고 끝난 상태의 value가 return 합니다. 그럼 최종적으로 root가 2인 그래프가 만들어집니다.