[C++] 백준 1717: 집합의 표현

문제

[C++] 백준 1717: 집합의 표현 GOLD 5
https://www.acmicpc.net/problem/1707

 

---

 

접근 방법

백준 1717번은 집합의 합집합과 포함 여부를 처리하는 문제로,

대표적인 Union-Find(Disjoint Set) 자료구조를 사용하는 문제다.

 

문제에서 수행하는 연산은 두 가지다.

1. 0 a b → a와 b를 같은 집합으로 합치기 (Union)
2. 1 a b → a와 b가 같은 집합인지 확인 (Find)

따라서 핵심은 각 원소가 어떤 집합에 속해 있는지를 효율적으로 관리하는 것이다.

 

이를 위해 parent 배열을 사용한다.

vector<int> parent;

 

• parent[i] : i의 부모 노드
• 초기에는 모든 원소가 자기 자신을 부모로 가진다.

for (int i = 1; i <= N; i++)
    parent[i] = i;​

 

Find (대표 노드 찾기)

int find(int x)
{
    if (parent[x] == x)
        return x;
    else
        return parent[x] = find(parent[x]);
}​

 

• 어떤 노드가 속한 집합의 대표 노드(루트) 를 찾는다.
• parent[x] = find(parent[x]) 를 통해
  경로 압축(Path Compression) 을 수행한다.
  → 이후 탐색 속도가 매우 빨라진다.

 

Union (집합 합치기)

void unionfunc(int a, int b)
{
    a = find(a);
    b = find(b);

    if (a != b)
        parent[b] = a;
}

• a와 b의 대표 노드를 찾은 뒤
• 서로 다르면 하나를 다른 쪽에 연결

→ 두 집합을 하나로 합친다.

같은 집합인지 확인

bool check(int a, int b)
{
    a = find(a);
    b = find(b);

    return a == b;
}​

두 노드의 대표 노드가 같으면 같은 집합에 속해 있는 것이다.

 

구현 시 주의할 점

• 초기화가 매우 중요하다.
  모든 원소는 처음에 자기 자신을 부모로 가져야 한다.
• find 함수에서 경로 압축을 반드시 적용해야 시간 초과를 방지할 수 있다.

parent[x] = find(parent[x]);

• union 연산 시에는 반드시 대표 노드끼리 연결해야 한다.
  (단순히 parent[b] = a 하면 안 됨 → find 후 연결)

 

 

---

 

코드

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

int N, M;
vector<int> parent;

int find(int x)  // 대표 노드 찾기
{
	if (parent[x] == x)
		return x;
	else
		return parent[x] = find(parent[x]);
}
void unionfunc(int a, int b)  // 합집합
{
	// 대표 노드 찾기
	a = find(a);  
	b = find(b);

	// 대표 노드끼리 연결
	if (a != b)
		parent[b] = a;
}
bool check(int a, int b)  // 두 노드가 같은 집합인지 확인
{
	a = find(a);
	b = find(b);

	if (a == b)
		return true;

	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	parent.resize(N + 1, 0);
	for (int i = 1; i <= N; i++)
		parent[i] = i;

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

		if (a == 0)
			unionfunc(b, c);
		else
		{
			bool ret = check(b, c);

			if (ret)
				cout << "YES" << '\n';
			else
				cout << "NO" << '\n';
		}
	}
}