집합 (유니온 - 파인드)

1. 집합

---

• 집합은 코딩테스트나 알고리즘에서 순서와 중복이 없는 원소들을 가지는 자료구조를 뜻한다.
  • 예를 들어, A = {1 ,6, 6, 6, 4, 3} 일때 A를 집합으로 생각하면 {6,3,4,1} 이런 식으로 정리 될 것이다.
• 코딩테스트에서는 주로 상호 배타적 집합에 집중하게 된다.
  • 상호 배타적 집합이란 A와 B라는 집합이 있을 때
  • 서로간의 교집합이 없는 집합을 뜻한다.
• 그 이유는, 그래프 문제에 사이클을 확인하는 경우가 많은데 이때 상호 배타적 집합 개념을 활용해서 문제를 풀기 때문이다.

 

 

2. 집합의 연산

---

주로 집합은 트리로 표현하게 된다. 또한 상호 배타적 집합을 나타내기 때문에 배열을 사용해서 구현한다.

• 이때 각 집합은 대표 원소가 있어야 한다.
• 대표 원소는 집합을 트리로 나타낼 때 루트가 되는 노드가 대표 원소가 된다.

집합을 배열로 표현하는 방식은 아래와 같이 표현할 수 있다.

• 현재 노드가 3이고, 부모 노드가 9인 경우
• Board[3] = 9; 
• 인덱스가 현재 노드를 가리키고, 값이 부모 노드를 가리킨다.

아래와 같은 상호 배타적 집합이 있을 때 하나의 배열로 표현이 가능하다.

• 현재 노드가 루트 노드라면 인덱스 값이 자기 자신이 된다. Board[1] = 1;

 

 

3. 유니온 파인드

---

집합 알고리즘에서 주로 쓰이는 연산은 합치기와 탐색이다.

이때 합치기는 Union 이라고 하고 탐색은 Find 라고 해서, 이 둘을 합친 알고리즘을 유니온-파인드 알고리즘이라고 한다.

 

3- 1. 파인드 연산

• 파인드 연산은 특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다.
• 두 노드의 루트 노드가 같다면 두 노드는 같은 집합에 속하는 의미이다.
• 코드적으로 생각하면, 재귀를 통해 자신의 루트가 자기 자신인 경우 일때 까지 탐색해서 리턴하면 된다.
• 파인드 연산을 좀 더 빠르게 하기 위해서 경로 압축이라는 것을 할 수 있다.
  • 경로 압축은 집합 형태를 유지하면서, 트리 높이를 줄이는 방식이다.
  • 아래 그림과 같은 동작을 하게 된다.
    • 왼쪽 그림의 경우 4는 계속 올라가면서 1이라는 루트를 찾아야 하지만
    • 오른쪽 경우는 한번에 루트 노드를 찾을 수 있게 된다.

 

3 -2. 유니온 연산

• 유니온 연산은 두 집합을 합치는 연산이다. 다시 말해 두 집합의 루트를 같도록 만드는 연산이다.
• 한가지 집합을 다른 집합에 붙인다면
  • 한 집합은 그대로 유지하고
  • 다른 집합의 루트 노드였던 노드의 값만 변하면 된다.
• 이때 각 노드들은 랭크라는 것을 가지게 하여 효율적으로 유니온 연산을 수행한다.
  • 랭크는 현재 노드를 기준으로 해서 가장 깊은 노드까지의 길이를 말한다.
  • 트리는 깊어질수록 연산 비용이 커지기 때문에 최대한 트리가 낮게 유지되는 것이 효율적이다.
  • 두 집합의 루트의 랭크를 비교해서 랭크 기반 유니온 연산을 할 수 있다.
    • 한쪽의 랭크가 더 큰 경우 (A의 랭크가 2고 B의 랭크가 1인 경우)
      • A쪽으로 B 집합을 합치게 되면, 랭크가 그대로 유지되기 때문에 트리의 깊이가 그대로 유지되어 효율적인 연산이 가능하다.
    • 랭크가 같은 경우는 아무쪽으로나 붙여준 다음 붙여준 쪽의 루트의 랭크를 하나 증가 시켜주어야 한다.

 

 

3 - 3.유니온 파인드 구현하기

#include <iostream>
#include <vector>
using namespace std;

int Board[1002];
int Rank[1002];

//루트 찾기
int Find(int x)
{
	if (Board[x] == x)
		return x;
	Board[x] = Find(Board[x]); //경로 압축

	return Board[x];
}

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

	if (rootX != rootY)
	{
        //랭크 비교
		if (Rank[rootX] < Rank[rootY])
		{
			Board[rootX] = rootY;
		}
		else if (Rank[rootX] > Rank[rootY])
		{
			Board[rootY] = rootX;
		}
		else //랭크 같으면 아무대나 붙이고 붙인 쪽 랭크 하나 올려주기
		{
			Board[rootY] = rootX; //Y의 루트를 X로
			Rank[rootX]++;		  //X의 랭크 증가
		}
	}	
}


vector<bool>solution(int k, vector<vector<char>> operations)
{
	vector<bool> answer;

	for (int i = 0; i < k; ++i)
	{
		Board[i] = i;
		Rank[i] = 0;
	}

	for (int i = 0; i < operations.size(); ++i)
	{
		if (operations[i][0] == 'u')
		{
			Union(operations[i][1] - '0', operations[i][2] - '0');
		}
		else if (operations[i][0] == 'f')
		{
			if (Find(operations[i][1] - '0') == Find(operations[i][2] - '0'))			
				answer.push_back(true);			
			else
				answer.push_back(false);
		}
	}
	return answer;
}


int main()
{
	vector<vector<char>>operations1 = { {'u','0','1'},{'u','1','2'}, {'f','0','2'} };
	vector<vector<char>>operations2 = { {'u','0','1'},{'u','2','3'}, {'f','0','1'}, {'f','0','2'} };

	vector<bool> ans1 = solution(3, operations1);
	for (auto a : ans1)
		cout << a << " ";

	vector<bool> ans2 = solution(4, operations2);
	for (auto a : ans2)
		cout << a << " ";
}