[백준/C++] 집합의 표현 (No. 1717)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 두 원소가 같은 집합에 있는지 찾는 것과 두 집합을 합치는 연산을 구현하면 쉽게 해결할 수 있는 문제다.

 

먼저 1차원 배열을 만든다.

이 배열에는 특정 원소의 부모 원소 값이 저장된다.

 

그러므로 이를 이용해 부모 원소를 따라가다 보면 array[i] 에 저장된 값이 i인 원소가 나타나는데, 이 때 i가 이 집합의 대표 원소가 된다.

 

즉, 두 원소가 속한 집합이 같은지를 찾기 위해서는 array를 이용해 대표 원소가 같은지 비교하면 해결할 수 있다.

 

이제 두 집합을 합치는 방법을 알아보자.

 

두 원소가 속한 집합을 합치는 방법도 간단하다. 

 

먼저 두 원소 a, b의 대표 원소를 찾는다. 이제 a, b의 대표원소를 pA, pB라고 하자.

 

그러면 일정한 규칙에 따라 array[pA]와 array[pB]의 값을 pA, pB 중 하나로 변경하면 두 집합은 합쳐지게 된다.

만약 규칙이 가장 작은 원소를 대표값으로 하는 것이라면 pA<pB인 경우 array[pA] = array[pB] = pA로 변경하면 된다.

 

+ 추가로 이대로 구현하면 시간초과가 나게 된다. 왜냐하면 같은 집합에 속해있는지 판단하기 위해 부모 원소를 찾는 과정이 반복되기 때문이다.

그러므로 부모 원소를 찾을 때, 지나온 원소들의 부모 원소 값을 전부 대표 원소 값으로 바꿔주면 시간복잡도가 O(N)이 된다.

 ex) 10이 속한 집합의 대표 원소가 1 이고, 10이 거쳐온 부모 노드가 7, 6, 5 라면 대표 원소를 찾은 뒤10, 7, 6, 5의 부모노드를 1로 바꿔주면 된다. 

 

 

​

[아이디어 정리]

1. 배열을 만든 뒤 배열에 부모노드를 저장한다.
2. 특정 원소 두개가 같은 집합에 있는지 비교하기 위해서는 부모노드를 반복 탐색해 대표 원소를 찾고, 그 대표원소의 값이 같은지 비교한다.
3. 반복적으로 부모노드를 거치면 효율이 좋지 않기 때문에 대표 원소를 찾을 때, 거쳐온 노드들의 부모 노드를 대표 원소 값으로 변경해 준다.

 

 

 

Code

 

 

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

int findPar(vector<int> &p, int nowN)
{
	int tmp = nowN;
	while (p[tmp] != tmp) {
		tmp = p[tmp];
	}
	int prev;
	while (p[nowN] != nowN) {
		prev = nowN;
		nowN = p[nowN];
		p[prev] = tmp;
	}
	return tmp;
}

void UnionPar(vector<int>& p, int a, int b)
{
	int parA = findPar(p, a), parB = findPar(p, b);
	int tmp= min(parA, parB);
	p[parA] = tmp, p[parB] = tmp;

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector<int> p(n+1);
	for (int i = 0; i < n + 1; i++) {
		p[i] = i;
	}
	int q, a, b;
	for (int i = 0; i < m; i++) {
		cin >> q >> a >> b;
		if (q == 0)
		{
			UnionPar(p, a, b);
		}
		else
		{
			int aa= findPar(p, a), bb= findPar(p, b);
			if (findPar(p, a) == findPar(p, b))
			{
				cout << "YES\n";
			}
			else 
			{
				cout << "NO\n";
			}
		}
	}

	return 0;
}

 

---

기본적인 Union - Find 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제였다.

 

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