백준 1717 집합의 표현

문제 링크 : https://www.acmicpc.net/problem/1717

※선행해야 할 알고리즘 : Disjoint-set(Union-Find)

* 다음 문제는 Disjoin-set 문제의 기초 문제입니다. 이해 후 하단의 문제들을 풀어보시기 바랍니다.

 - 4195 친구 네트워크

 - 1976 여행가자

 - 10775 공항

 - 9938 방청소

 - 3780 네트워크 연결

 - 3430 용이산다

 - 2843 마블

* Cpp 사용자 분들은 Cin 사용 시, 시간초과가 날 수 있습니다.

 - 초과나는 원인 및 테스팅은 하단 그림과 같습니다.

 - 또한 cin의 endl은 강제로 fflush를 하여 시간을 더 잡아먹습니다.

 - 결론 : 백준에서는 cin보다 scanf를 사용하세요!

유니온 파인드(Union-Find)

① 유니온 파인드란?

▷ 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.

▷ 상호 배타적 집합(Disjoint-set)이라고도 합니다.

▷ 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

▷ 2가지 연산으로 이루어져 있습니다.

   ▶ Find : x가 어떤 집합에 포함되어 있는지 찾는 연산

   ▶ Union : x와 y가 포함되어 있는 집합을 합치는 연산

② 그림으로 보는 Union-Find

위와 같이, 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만듭니다.

i : 노드번호, P[i] : 부모 노드 번호 를 의미하며, 즉 자기 자신이 어떤 부모에 포함되어 있는지를 의미합니다.

정리하면, Parent[i] = i로 간단히 표현할 수 있습니다.

Union(1,2); Union(3,4) 를 해주어 위와 같이 노드를 연결해봅시다.

위와 같이 표에 표현이 됩니다. 2번째 인덱스에 '1'이 들어가고, 4번 인덱스에 '3'이 들어가는 것을 보실 수 있습니다.

이와 같이 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합칩니다. 이것을 합침(Union) 과정이라고 말할 수 있습니다.

위와 같이 1, 2, 3이 연결될 때는 어떻게 표현이 될까요?? 바로 아래와 같이 표현이 됩니다.

1과 3은 부모가 다르기 때문에 '1과 3이 연결되었는지' 파악하기 힘이 듭니다. 이에 재귀함수가 사용됩니다.

3의 부모인 2를 먼저 찾고, 2의 부모인 1을 찾아, 결과적으로 3의 부모는 1이 되는 것을 파악하는 것입니다.

Union의 과정이 수행된 후에는 다음과 같은 표로 바뀝니다.

결국 1,2,3의 부모는 모두 1이기 때문에 이 세 가지 노드는 모두 같은 그래프에 속한다는 것을 알 수 있습니다.

해당 경로를 바꿔주는 과정은 아래와 같은 그림으로 변하게 됩니다.

Algorithm : 0일 때 합집합(Union)을 실시하고, 1일 때 Find를 실시

//kuklife.tistory.com #include<iostream> #include<vector> #include<cstdio> using namespace std; vector<int> set; int F(int x) //find { if (x == set[x]) return x; else return set[x] = F(set[x]); } void U(int x, int y) //union { x = F(x); y = F(y); set[x] = y; } int main() { vector<string>result; int n, m; scanf("%d %d", &n, &m); for (int i = 0; i <= n; i++) set.push_back(i); for (int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); if (!a) U(b, c); else { if (F(b) == F(c)) printf("YES\n"); else  printf("NO\n"); } } return 0; }