https://www.acmicpc.net/problem/1717
문제
> 초기에 n+1개의 집합 {0}, {1}, {2},..., {n}이 있다.
> 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
> 집합을 표현하는 프로그램을 작성하시오.
> 첫째 줄에 n, m이 주어진다.
> m은 입력으로 주어지는 연산의 개수이다.
> 다음 m개의 줄에는 각각의 연산이 주어진다.
> 합집합은 0 a b의 형태로 입력이 주어진다.
> 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다.
> 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다.
> 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.접근
Union과 Find를 사용한다.
Find는 들어온 변수에 대해 이 변수의 parent값이 변수와 같다면 초기에 주어진 뿌리값이랑 같으므로 그대로 반환하고
다르다면 어딘가의 집합에 속해있다는 뜻이므로 재귀로 이를 따라가 준다. Find(parent(a))로 처음 들어온 a의 뿌리 값의 뿌리를 찾는다. 그리고 최종적으로 가장 상위 뿌리(parent(a) == a를 만족하는)가 반환된다.
Union에선 이 Find를 이용해 들어온 a와 b의 뿌리를 가져온다.
두 원소를 하나의 집합으로 합쳐야하므로 둘 중 하나의 parent값을 다른 하나의 값으로 바꾼다.
예제를 예로 들면 0 1 3을 통해 1과 3이 Union된다.
난 뒷 변수값을 앞변수의 뿌리로 바꾸도록 했으므로 여기서
parent(1) == 1, parent(3) == 1로 된다.
1 1 7은 둘의 Find값을 비교하는 것이므로 parent(1)은 1이고 parent(7)은 7이므로 서로 달라 NO가 나온다.
0 7 6으로 parent(7) == 7, paretn(6) == 7
1 7 1로 parent(7)은 7, parent(1)은 1로 NO가 나오고
0 3 7로 parent(3) == 1, parent(7) == 1이 된다.
앞서 0 1 3에서 3의 뿌리가 1로 바뀌었기 때문에 여기서 7 또한 영향을 받은 3으로 인해 1로 바뀐다.
그럼 여기서 앞서 0 7 6을 통해 7에게 영향을 받아 parent가 7이 된 6도 7의 parent가 1이 됐기 때문에 1로 parent가 변한다.
0 4 2를 통해 parent(4) == 4, parent(2) == 4
0 1 1을 통해 parent(1) == 1, parent(1) == 1이라 if문이 실행 안되고 종료되고
1 1 1을 통해 1은 parent가 같아서 YES가 나온다.
결과적으로 1,3,6,7은 parent가 1로 같은 집합
2,4는 parent가 4로 같은 집합
5는 parent가 5로 총 3개의 집합이 있다.
문제해결
> 문제에 n+1개의 집합의 초기 상태를 자기자신만 원소로 가지고 있는 집합으로 주었기 때문에 이를 parent 배열로 인덱스는 자기자신, 값도 자기자신으로 가져 집합의 형태를 만든다.
> 그리고 입력받은 f에 대해 parent(f)가 자기자신이면 그대로 반환하고 아니면 재귀로 뿌리를 찾아 반환하는 Find 메소드를 정의한다.
> 입력받은 두 수의 뿌리를 같게 동기화해 집합화 하는 Union 메소드를 정의한다.
> 연산횟수 M만큼 while문에서 세 변수를 입력받는다.
> 0이면 Union연산으로 집합화, 1이면 Find로 서로의 뿌리를 비교해 같으면 YES, 다르면 NO를 출력한다.코드
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int parent[1000001];
int Find(int f)
{
if (parent[f] == f) return f;
return parent[f] = Find(parent[f]);
}
void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if (a != b) parent[b] = a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
for (int i = 0; i <= N; i++) parent[i] = i;
while (M--)
{
int cmd, a, b;
cin >> cmd >> a >> b;
if (cmd)
{
cout << (Find(a) == Find(b) ? "YES" : "NO") << '\n';
continue;
}
Union(a, b);
}
}
후기
Union-Find를 더 이해하기 위해 풀어봤다. 기본을 요하는 문제라 딱 원하는 문제였다.
