C++ / 백준 / 1717 / 집합의 표현

문제

 

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

 

 

문제풀이

 

숫자 두 개가 속한 집합을 합치거나, 같은 집합인지 확인을 하는 유니온 파인드의 기본 문제이다.

집합 중 가장 작은 수를 나타내는 parent 벡터를 이용한다.

집합의 가장 작은 수를 찾는 find 함수, 두 집합을 합치는 Union함수, 두 숫자가 같은 집합인지 확인하면 isUnion함수를 선언한다.

 

int find(vector<int>&parent, int num) {
	if (parent[num] == num) return num;
	return parent[num] = find(parent, parent[num]);
}

집합의 가장 작은 수가 num과 같다면 바꿀 필요가 없으므로 그대로 둔다.

그렇지 않으면 parent[num]을 가장 작은 값으로 바꾼다.

ex) parent[3]=2, parent[5]=3 이라면 parent[5]=2

 

void Union(vector<int>&parent, int num1, int num2) {
	num1 = find(parent, num1), num2 = find(parent, num2);
	if (num1 == num2) return;
	if (num1 < num2) swap(num1, num2);
	parent[num1] = num2;
}

두 숫자의 집합을 합치는 함수이다.

먼저 숫자의 집합 중 가장 작은 숫자를 각각 찾는다.

둘이 같은 집합이라면 넘어간다.

그렇지 않으면 집합의 값은 작은 값이 되어야 하므로 두 숫자를 바꾼다.

그다음 parent[큰수] = 작은 수로 바꾼다.

 

bool isUnion(vector<int>&parent, int num1, int num2) {
	if (find(parent, num1) == find(parent, num2)) return true;
	return false;
}

둘이 같은 집합인지 확인하는 함수이다.

find함수를 사용하여 둘의 값이 같다면 같은 집합이므로 true를, 다르다면 false를 return 하면 된다.

 

코드

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

int find(vector<int>&parent, int num) {
	if (parent[num] == num) return num;
	return parent[num] = find(parent, parent[num]);
}

void Union(vector<int>&parent, int num1, int num2) {
	num1 = find(parent, num1), num2 = find(parent, num2);
	if (num1 == num2) return;
	if (num1 < num2) swap(num1, num2);
	parent[num1] = num2;
}

bool isUnion(vector<int>&parent, int num1, int num2) {
	if (find(parent, num1) == find(parent, num2)) return true;
	return false;
}

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

	int N(0), M(0);
	cin >> N >> M;
	vector<int>parent(N + 1, 0);
	for (int idx = 0; idx <= N; ++idx) parent[idx] = idx;

	for (int idx = 0; idx < M; ++idx) {
		int cmd(0), num1(0), num2(0);
		cin >> cmd >> num1 >> num2;
		if (cmd == 0) Union(parent, num1, num2);
		else if (cmd == 1) isUnion(parent, num1, num2) ? cout << "YES\n" : cout << "NO\n";
	}
}