[백준]집합의 표현(C++)

문제

집합의 표현-골드5
유니온파인드라는 알고리즘을 사용하는 문제이다.

문제설명

초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 $1$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 $a$와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제한

$1 ≤ n ≤ 1\,000\,000$ 

$1 ≤ m ≤ 100\,000$ 

$0 ≤ a, b ≤ n$ 
$a$, $b$는 정수
$a$와 $b$는 같을 수도 있다.

문제분석

n을 입력받아 부터 n까지의 n+1개의 집합을 생성한다.
m을 입력받아 m번의 연산을 수행한다.
0 a b의 입력을 받으면 a와 b를 동일한 집합으로 합친다.
1 a b의 경우 a, b가 동일한 집합이면 YES, NO를 출력하도록 한다.

해결방법

0 a b, 1 a b의 입력만 잘처리하면 되는 문제이다.
먼저 n의 최대치에 해당하는 크기의 배열을 선언하였고 이 배열에는 각 숫자의 root값을 저장하도록 한다.

root

int root(int a)
{
	if (a == arr[a]) return a;
	else return arr[a]= root(arr[a]);
}

숫자의 root를 찾는 함수이다. 전달받은 숫자와 숫자의 root값이 동일하면 a를 다르다면 재귀를 이용해 root를 구하고 배열에 저장되어있는 root값을 바꾸어 준다.

1. 0 a b의 경우 root함수를 이용하여 a, b의 root를 찾고 두 root를 비교하여 작은 쪽에 합하도록 한다.
2. 1 a b의 경우 root함수를 이용하여 a, b의 root를 찾고 동일한지 확인하여 그에 맞는 문구를 출력하도록 한다.

코드

#include<iostream>
using namespace std;
int arr[1000001];
int root(int a)
{
	if (a == arr[a]) return a;
	else return arr[a]= root(arr[a]);
}
int main() {
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n;
	for (int i = 0; i <= n; i++)
	{
		arr[i] = i;
	}
	cin >> m;
	int oper, a, b;
	for (int i = 0; i < m; i++)
	{
		cin >> oper >> a >> b;
		if (oper == 0)
		{
			a = root(a);
			b = root(b);

			if (a < b) arr[a] = arr[b];
			else arr[b] = arr[a];
		}
		else {
			a = root(a);
			b = root(b);
			if (a == b) cout << "YES\n";
			else cout << "NO\n";
		}
	}

	return 0;
}

후기

맞긴했지만 시간초과와 틀린경우가 많다.
시간초과의 경우 입출력을 사용하는 경우가 많아서 발생하였다고 생각하였다.

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이를 위한 해결방법으로 입출력 속도를 향상 시킬수 있도록 위의 코드를 넣어주었고 더이상 시간초과는 발생하지 않았다.

그 다음으로 틀린경우에는 문제의 이해를 잘못해서 생긴 문제였다. n을 입력 받았을때 0부터 n까지 n+1개의 집합을 생성하여야 했는데 입력받은 n값이 n+1이라고 잘못생각을 하여 집합을 n개 생성하여 틀린 결과가 나왔다. 이를 발견하고 배열의 크기를 1증가시켜 1000001로 바꾸어주었고 집합을 생성하는 for문에서 i<=n으로 바꾸어 문제를 해결하였다.

방법을 알면 쉽지만 모르면 어려워지는 문제중 하나인것 같다.