[알고리즘] Union FInd

치치·2025년 1월 25일
알고리즘

알고리즘C++

목록 보기
18/24
post-thumbnail

유니온 파인드

  • 서로소 집합을 관리하기 위한 자료구조이다
  • 어떤 노드가 다른 노드와 연결되어있는지 즉, 같은 집합에 속하는지 확인할 때 사용한다 (합집합 찾기)

서로소 집합이란?

  • 공통으로 포함하는 원소가 없는 두 집합이다
  • ex) {1, 2, 3 }, {4, 5, 6}은 서로소 집합이다

크게 두가지 함수로 나눠서 살펴보자

1. Find (탐색)

어떤 원소가 속한 집합(부모)을 찾는 연산이다. 재귀를 사용하여, 최상위 루트 노드를 반환한다 (재귀를 사용하여 경로를 압축함)
즉, 루트 노드가 그 집합의 대표인 것이다

2. Union (합집합)

두 집합을 하나로 합치는 연산이다
즉, 두 개의 집합을 하나의 집합으로 합치는 작업인 합집합을 수행한다


그림을 예시로 설명

일단 코드를 보기전에 전체적인 흐름을 보고 가보자

  1. 초기상태에서는 각 요소들이 각각의 독립적인 집합으로써 존재한다
    따라서, 각 노드가 자기 자신을 부모로 갖는 root노드가 된다
    -> root노드는 트리 구조에서 더 이상 부모 노드가 없는 가장 높은 노드를 의미함
    -> Union하지 않은 상태에서 Find함수를 호출하게 되면 모든 요소들이 자신의 부모와 같은 상태이기 때문에 항상 자기 자신을 반환한다
    -> 코드 상 부모배열의 크기가 7인데, 수와 인덱스를 맞추기 위해서 0번째 인덱스는 사용하지 않겠다

  2. 만약 Union함수를 사용해서 1과2, 2와 3, 1과 4을 연결했다면?

  • Union(1, 2); -> 의미 자체는 1과 2가 속해있는 집합의
  • Union(2, 3);
  • Union(1, 4);
    그림은 부모 노드의 값들이 모두 1이다
    -> 연결된 노드들의 부모노드를 서로 비교하여 그 값으로 갱신해주는 것
    -> 여기서는 1이 최상위 root노드가 되어서 집합의 대표이다. 그래서 부모노드의 값도 다 1이 된 것
    -> 1, 2, 3, 4는 모두 같은 집합에 속하게 되었다
    {1, 2, 3, 4}, {5}, {6}
  1. Union함수는 어떻게 동작한 것 일까?
    -> Union함수는 집합의 root노드끼리 비교하여 더 작은 값을 기준으로 부모배열의 값을 갱신한다

  • Union(1,2); 함수를 호출하면 즉시, 매개변수로 받은 인자의 root노드를 찾아야한다 -> Find함수를 사용하여 탐색
    위에서 말한 것 처럼 Find함수는 해당 원소의 집합의 대표를 찾는 함수이다.
    -> 즉, 최상위 root노드를 찾는 것
    -> 찾아낸 root노드의 값을 비교한 뒤 작은값을 기준으로 부모 배열을 갱신한다.
    -> 결국 같은 집합에 있는 원소들의 부모노드값은 그 집합의 대표 값과 같아지게 된다.

  • Union함수를 사용하기 위해서는 Find함수의 개념을 알아야한다!
    -> Find함수는 부모노드의 값과 현재 값이 같다면 그 값을 반환한다
    -> 즉, 최상단root노드라면 반환하는 것! (부모가 자신이라면)
    -> 그렇지 않다면, 어떤 노드랑 연결되있기 때문에 자기 자신이 부모가 아니라는 소리죠

Find함수를 사용하지 않았을 경우!
Union(2,3); 호출했을 때, 최상위 root노드의 값으로 변경하는 게 아닌! 그냥 부모노드의 값으로 변경하기 때문에 3의 부모노드는 2가 된다

  • 이러면 1과 3은 같은 집합일까?
    -> 실제로 {1, 2, 3}은 같은 집합이다! 하지만 부모 노드의 값이 다르다
    -> Find함수를 사용해서 이 값을 갱신시켜주면 집합의 대표 값으로 변경된다

    (실제 수업시간에 코드를 짰을때, 이렇게 짰었다 ...)
    root노드의 값은 제대로 비교를 해놓고 정작 부모노드의 값을 root노드로 변경한 것이 아닌 그냥 부모노드로 갱신해버렸다
  1. Find함수 자세히 보기
  • Union(1,2);를 호출했다고 가정하자
    각각의 집합인 1과 2의 요소와 부모노드의 값이 같다 == 각 노드가 root노드다
    -> root노드끼리 값을 비교하여 더 작은쪽이 집합의 대표가 된다
  • 두 노드가 연결이되고, 노드2의 부모노드는 1이 된다
  • Union(2,3);을 호출하여 더 연결해보자
    -> 노드3은 부모노드와 값이 같기 때문에 root노드가 맞다
    -> 노드2의 부모노드는 1이기 때문에, 재귀함수를 사용하여 값을 반환해야한다
    -> 노드2의 부모노드의 값은 1이기 때문에 Find(1)호출
    -> 반환된 값은 1이다
  • 1 < 3 이기 때문에 노드3의 부모노드도 1이 되고 {1, 2, 3}은 같은 집합이 되었다

단계 별 코드

  1. 부모노드의 값을 담을 부모 배열 생성
    -> 노드는 총 6개로 구성, SIZE를 7로 잡고 0번째 인덱스는 사용하지 않는다 (편하게 볼려고)
  2. 생성자에서 부모 배열안의 값을 해당 노드의 값으로 지정
  3. Find(int x)함수
    -> 최상단 root노드라면 노드의 값을 반환
    -> 즉, 부모 노드의 값과 자신의 값이 같다면, 위의 부모가 따로 없다는 것 == 최상위 root노드
    -> 그렇지 않다면, 재귀를 사용해 root노드를 탐색한다
    -> 이 과정 자체가 경로 압축 (Path compression)
  4. Union(int x, int y)함수
    -> 합집합 과정으로, 최상위 노드를 Find함수를 통해 얻어내고 그 값을 비교하여 부모 노드의 값을 갱신시켜준다
  5. Same(int x, int y)함수
    -> 부모노드가 서로 같은지를 판단하는 T/F함수
    -> 서로 같은 집합이라며 부모노드가 같겠죠

유니온 파인드 전체코드

#include <iostream>
#define SIZE 7
using namespace std;

class Graph
{
private:
	// 부모 배열
	int parent[SIZE];


public:
	Graph()
	{
		for (int i = 1; i < SIZE; i++)
		{
			parent[i] = i;
		}
	}

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

		else
		{
			return parent[x] = Find(parent[x]);
		}
	}

	void Union(int x, int y)
	{
		x = Find(x);
		y = Find(y);

		if (x < y)
		{
			parent[y] = x;
		}
		else
		{
			parent[x] = y;
		}
	}

	bool Same(int x, int y)
	{
		return Find(x) == Find(y);
	}
};

int main()
{
#pragma region 유니온 파인드

	Graph graph;

	graph.Union(1, 2);
	graph.Union(2, 3);
	graph.Union(3, 4);

	// root노드가 같다면 같은 집합이다
	cout << graph.Same(1, 3) << endl; // true 1
	cout << graph.Same(1, 5) << endl; // false 0

#pragma endregion

	return 0;
}

  • {1, 2, 3, 4}는 같은 집합
  • {1, 2, 3, 4}, {5}, {6}

    출력값: True = 1 False = 0


유니온 파인드 시간복잡도(보충)

O(M log N)
M : 연산의 개수
N : 노드의 개수
M이 N²에 가까울 때 O(N² log N)이 된다

  • Find와 Union의 시간복잡도는 트리구조로 이루어져있기 때문에, logn의 시간복잡도이다
  • 실제값은 O(a(n))으로 아커만 함수의 역함수이다 (매우 느리게 증가하는 함수)
  • O(a(n))을 근사적으로 logn으로 봐도 된다

Find : 경로 압축을 사용하여 root노드를 찾아내기 때문에 O(a(n))으로 표기하지만, 실제로 n이 커지더라도 a(n)은 매우 작은 값에 가까워 그냥 상수시간에 동작한다고 본다
Union : 두 집합을 합치는 연산으로, Union by Rank를 사용하기 때문에 상수 시간이 걸린다
Union by Rank : 트리의 높이가 작은 집합을 트리가 높은 집합에 붙여주는 방식
-> 우리가 배운걸로 생각하면, 서로의 집합을 병합할 때 하나의 root노드로 통일시켜주는 방식

유니온 파인드의 연산의 수(M) x 유니온 파인드 (logN)

-> 유니온 파인드의 연산의 수 (M) : Find와 Union을 몇번 수행했는지, (호출)


유니온 파인드 코드 다시보기

#include <iostream>
#include <vector>
#define SIZE 6
using namespace std;



class Graph
{
private:
	int parent[SIZE]; // 부모 배열


public:
	// 생성자에서 초기화
	Graph()
	{
		// 초기 상태는 각각의 집합
		for (int i = 0; i < SIZE; i++)
		{
			parent[i] = i;
		}
	}

	// root노드를 찾는 함수 (재귀)
	int Find(int x)
	{
		if (parent[x] == x)
		{
			return x;
		}
		else
		{
			parent[x] = Find(parent[x]);
		}
	}

	// 두 집합을 병합
	void Union(int x, int y)
	{
		// x,y의 root노드를 찾아옴 
		x = Find(x);
		y = Find(y);

		if (x < y)
		{
			parent[y] = x;
		}
		else
		{
			parent[x] = y;
		}
	}

	bool Same(int x, int y)
	{
		return Find(x) == Find(y); // root노드가 서로 같으면 같은 집합 true(1)
	}
};

int main()
{
	Graph graph;

	graph.Union(1, 2);
	graph.Union(1, 3);

	graph.Union(4, 5);

	cout << graph.Find(3) << endl; // 3은 1의 집합에 포함된 상태

	cout << graph.Same(1, 2) << endl; // true (1)
	cout << graph.Same(3, 5) << endl; // false(0)

	return 0;
}
profile
치치
뉴비 개발자
이전 포스트

[알고리즘] Topology Sort

다음 포스트

[알고리즘] Minimum Spanning Tree

0개의 댓글