[Baekjoon] 1717번: 집합의 표현

 

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

1717번: 집합의 표현

 

---

 

문제 해결 과정

착안

서로소 집합(분리 집합, disjoint set)을 사용하여, 유니온-파인드(union-find) 연산에 의해 포함 관계를 따지는 문제이므로 해당 자료 구조를 구현하여 문제를 해결하고자 하였다.

 

구현

이 문제에서는 데이터를 정수형의 기본 자료형이기 때문에 인덱스로 간주하여, 유니온-파인드 연산에서 사용할 부모를 나타내는 정보를 배열에 저장할 수 있으므로 배열로 구현하는 것이 메모리 / 실행 속도 면에서 더 효율적이다(오징어 게임의 상우 형이 말했던 것처럼 머리가 x나 나빠서 똥인지 된장인지 먹어보고 알았다).

 

또한, 평소에 전역 변수를 안 쓰는 프로그래밍 습관 때문에 지역 변수로 배열을 만들어 활용하여 해결했는데 나중에 이를 전역 변수로 바꾸어 다시 제출해보니 실행 속도가 향상되었다(52 ms $\rightarrow$ 36 ms).

 

(실패 과정) 초기 프로그래밍에서는 파인드 연산의 시간 복잡도가 $O(1)$이 되도록 프로그래밍 하지 못해서 시간 초과로 계속해서 문제 해결에 실패했었다. Find() 함수를 구현할 때, 유니온 연산에 의해서 새로운 집합들이 계속 연결되는 과정에서 원래 가리키던 부모가 더이상 해당 집합의 최상위 부모가 아니게 되는 경우가 발생하도록 프로그래밍 한 것이 문제였다. 이 부분을 해결하기 위해 파인드 연산을 수행할 때, 현재 요소의 부모를 가리키는 데이터가 그 집합의 최상위 부모를 가리키고 있지 않는 경우에는 최상위 부모를 가리키도록 다시 초기화해주었다.

* 연결 리스트로 구현한 경우의 코드는 별도로 포스팅에 포함하지 않음.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int* Sets = new int[1000001];

int Find(int a)
{
	if (a == Sets[a])
		return a;

	return Sets[a] = Find(Sets[a]);
}

void Union(int a, int b)
{
	if (a == b)
		return;

	int pa = Find(a);
	int pb = Find(b);
	if (pa == pb)
		return;

	Sets[pb] = a;
}

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

	int N, M, Op, A, B;
	cin >> N >> M;

	for (int i = 0; i < N + 1; i++)
		Sets[i] = i;

	while (M--)
	{
		cin >> Op >> A >> B;

		if (Op)
			cout << (Find(A) == Find(B) ? "YES" : "NO") << "\n";
		else
			Union(A, B);
	}

	delete[] Sets;
	return 0;
}

 

실행 결과

 

아래의 결과는 배열로 문제를 해결했을 때의 결과이고 위는 연결 리스트로 해결했을 때의 결과인데, 연결 리스트의 경우에는 각각의 노드가 차지하는 메모리를 포함해서 노드를 가리키는 포인터의 배열이 가지는 메모리 때문에 메모리를 더 많이 사용하는 결과가 나왔다.