[알고리즘] Union-Find와 사이클 판별&크루스칼 알고리즘

 

Union Find

유니온 파인드는 여러 원소가 속한 집합들을 빠르게 합치고,
특정 원소가 어떤 집합에 속하는지를 효율적으로 판단하는 알고리즘이다.

기본적으로 각 원소들의 부모를 저장하는 배열 parents를 두고, find 함수와 union 함수를 만들어 구현한다. 

 

처음에 각 원소들의 부모는 자기자신으로 설정되어있다. 

union 연산은 두 원소가 같은 부모를 가리키도록 설정한다. 

find 함수는 재귀적으로 원소의 부모를 타고 올라가 최상위 부모를 찾는다. 

최상위 부모가 동일하다면, 그 원소들은 같은 집합 내에 있다 (연결되어있다) 라고 판단할 수 있다. 

 

int find(vector<int>& parents, int n)
{
	if (parents[n] == n)
		return n;

	return parents[n] = find(parents, parents[n]);
}

void union_op(vector<int>& parents, int a, int b)
{
	int rootA = find(parents, a);
	int rootB = find(parents, b);

	if (rootA != rootB)
	{
		parents[rootB] = rootA;
	}
}

 

 

 

 

Union Find 응용) 사이클 판별 

예제 문제) BOJ 20040 사이클 게임

https://www.acmicpc.net/problem/20040

 

간선을 하나씩 이어나갈 때, 언제 사이클이 만들어지는지를 출력하는 문제이다. 

사이클이 만들어지는 경우 == 같은 부모를 갖는 정점끼리 잇는 경우!! 

int find(vector<int>& parents, int n)
{
	if (parents[n] == n)
		return n;

	return parents[n] = find(parents, parents[n]);
}

bool union_op(vector<int>& parents, int a, int b)
{
	int rootA = find(parents, a);
	int rootB = find(parents, b);
	if (rootA == rootB)
		return true;

	parents[rootB] = rootA;

	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<int> parents(n);
	for (int i = 0; i < n; i++)
		parents[i] = i;

	int cycleNum = 0;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;

		if (union_op(parents, a, b) && cycleNum == 0)
		{
			cycleNum = i + 1;
		}
	}
	
	cout << cycleNum;
}

 

 

 

 

Union Find 응용) 크루스칼 알고리즘 

모든 정점들을 연결하면서 가중치가 최소가 되도록 하는 트리를 최소 스패닝 트리(MST)라고 한다. 

최소 스패닝 트리를 구하는 대표적인 알고리즘이 크루스칼 알고리즘이며, 유니온 파인드를 사용한다. 

 

크루스칼 알고리즘은 다음과 같은 과정으로 요약된다. 

1) 모든 간선들을 배열에 넣고 가중치가 작은 순으로 정렬한다. 

2) 간선을 하나씩 확인하면서, 간선을 이루는 두 정점이 같은 부모를 가지는지 확인한다. 

3) 두 정점이 같은 부모를 가지지 않으면 그 간선을 연결한다.

4) 총 V-1개의 간선이 선택될 때까지 반복한다. 

 

크루스칼 알고리즘은 간선 개수가 적은 희소 그래프에서 사용하기 적합하다. 

간선 개수가 많은 경우에는 노드 중심의 프림 알고리즘을 사용하는 것이 더 적합하다. 

 

예제 문제) BOJ 1197 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

 

int find(vector<int>& parents, int n)
{
	if (parents[n] == n)
		return n;

	return parents[n] = find(parents, parents[n]);
}

void union_op(vector<int>& parents, int a, int b)
{
	int rootA = find(parents, a);
	int rootB = find(parents, b);

	if (rootA != rootB)
	{
		parents[rootB] = rootA;
	}
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int V, E;
	cin >> V >> E;

	vector<int> parents(V + 1);
	vector<pair<int, pair<int, int>>> edges;

	for (int i = 1; i < V + 1;i++)
	{
		parents[i] = i;
	}

	for (int i = 0; i < E; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		
		edges.push_back({ c, {a,b} });
	}
	sort(edges.begin(), edges.end());

	int answer = 0;
	int num = 0;
	for(int i = 0; i < edges.size(); i++)
	{
		int nowCost = edges[i].first;
		int nowA = edges[i].second.first;
		int nowB = edges[i].second.second;

		if (find(parents, nowA) == find(parents, nowB))
			continue;

		union_op(parents, nowA, nowB);
		answer += nowCost;
		num++; 

		if (num == V)
			break;
	}

	cout << answer;
}