문제 설명
정점의 개수 n과 유니온 파인드 쿼리 정보 queries가 주어질 때, 쿼리 타입에 따라 적절한 작업을 진행하고 쿼리 결과를 반환하는 solution 함수를 작성하시오.
쿼리 타입은 다음과 같이 2가지가 있습니다.
- [-1, x, y] - Union Query :
두 정점x와y를 동일 집합으로 병합합니다. - [-2, x, y] - Find Query :
두 정점x와y가 동일 집합에 포함되어 있으면true, 그렇지 않으면false를 반환합니다.
x, y는 1 이상 n 이하의 서로 다른 자연수입니다.
개념 설명
유니온 파인드 알고리즘(Union-Find Algorithm)은 상호배타적으로 이루어진 집합(분리 집합)을 효율적으로 표현, 연산하는 알고리즘입니다. 유니온 파인드 알고리즘을 적용하는 문제 상황에는 2가지 연산이 정의됩니다.
- Union : 서로 다른 두 분리 집합을 병합합니다. (합집합)
- Find : 한 원소가 어느 집합에 포함되어 있는지 판단합니다.
기초적인 유니온 파인드 알고리즘 작동 방식은 "[대표 유형] 유니온 파인드 알고리즘"를 참고할 수 있습니다.
Union By Rank/Size
유니온 파인드 알고리즘은 Union By Rank/Size 방법과 Path Compression 방법으로 2가지를 모두 사용하여 쿼리당 처리 속도를 대폭 줄일 수 있습니다.
먼저 Union By Rank/Size 방법은 서로 다른 분리 집합 트리를 병합(Union)하는 과정에서 높이/크기가 작은 트리를 큰 트리의 자식으로 병합하는 방법입니다.
다음과 같은 두 분리 집합 트리가 있을 때 정점 6과 정점 10을 병합한다고 가정합니다.
이때 루트 정점을 병합하는 과정에서 다음과 같은 두 가지 방법을 고려할 수 있습니다.
위의 두 가지 병합 방법 중에서 향후에 Union, Find 쿼리를 계속 진행할 때 더 최적화된 방법은 두 번째로 제시된 병합 방법입니다.
이처럼 분리 집합 트리의 높이 또는 트리 내 정점 개수를 기준으로 더 큰 트리의 루트 노드로 분리 집합 트리의 루트 노드를 설정하면 분리 집합의 크기가 N일 때 트리의 최대 높이는 임이 보장되며 모든 Union/Find 쿼리 당 의 시간복잡도를 갖습니다.
Path Compression
Path Compression 방식은 Find 쿼리를 진행하면서 내부 정점의 부모 정점을 루트 노드로 지정하여 트리를 평평하게 만드는 방식입니다.
다음과 같은 분리 집합 트리에서 10번 정점에 대해 Find 쿼리를 한다고 가정합니다.
Find 과정을 통해 10번 정점뿐만 아니라 4번 정점, 6번 정점 또한 루트 노드가 1번 정점임을 알 수 있습니다. 이때 Path Compression 최적화를 적용하면 다음과 같이 4, 6, 10번 정점의 부모 정점을 모두 1번 정점으로 설정할 수 있습니다.
또한 이를 정리하면 다음과 같습니다.
이처럼 트리의 높이를 낮추면 Find 쿼리에서 루트 노드를 찾기 위해 호출되는 재귀함수의 깊이를 줄일 수 있습니다.
제한 사항
n은 주어지는 정점의 개수이며 100,000 이하의 자연수입니다. 각 정점은 1 이상 n 이하의 정점번호를 가집니다.
queries는 아래와 같은 쿼리 정보를 100,000개 이하로 가집니다.
- [-1, x, y] :
두 정점x와y를 동일 집합으로 병합합니다. - [-2, x, y] :
두 정점x와y가 동일 집합에 포함되어 있으면true, 그렇지 않으면false를 쿼리 순서대로 반환합니다.
x, y는 1 이상 n 이하의 서로 다른 자연수입니다.
예시 테스트케이스 설명
| 테스트케이스 번호 | n | queries | return |
|---|---|---|---|
| 1 | 5 | [[-1,3,5],[-1,4,1],[-2,4,3],[-2,4,1]] | [false,true] |
| 2 | 9 | [[-1,2,7],[-2,2,7],[-2,2,7],[-1,6,9],[-1,6,8],[-1,9,2],[-1,2,3],[-2,3,8],[-1,9,7],[-2,6,9]] | [true,true,true,true] |
| 3 | 5 | [[-1,3,5],[-2,5,1],[-1,1,5],[-1,3,5],[-1,2,5],[-1,1,2],[-2,5,4]] | [false,false] |
1번 테스트케이스 설명
- 쿼리 [-1,3,5] : {1}, {2}, {3,5}, {4}
- 쿼리 [-1,4,1] : {1,4}, {2}, {3,5}
- 쿼리 [-2,3,4] : false
- 쿼리 [-2,4,1] : true
2번 테스트케이스 설명
- 쿼리 [-1,2,7] : {1}, {2,7}, {3}, {4}, {5}, {6}, {8}, {9}
- 쿼리 [-2,2,7] : true
- 쿼리 [-2,2,7] : true
- 쿼리 [-1,6,9] : {1}, {2,7}, {3}, {4}, {5}, {6,9}, {8}
- 쿼리 [-1,6,8] : {1}, {2,7}, {3}, {4}, {5}, {6,8,9}
- 쿼리 [-1,9,2] : {1}, {2,6,7,8,9}, {3}, {4}, {5}
- 쿼리 [-1,2,3] : {1}, {2,3,6,7,8,9}, {4}, {5}
- 쿼리 [-2,3,8] : true
- 쿼리 [-1,9,7] : {1}, {2,3,6,7,8,9}, {4}, {5}
- 쿼리 [-2,6,9] : true
3번 테스트케이스 설명
- 쿼리 [-1,3,5] : {1}, {2}, {3,5}, {4}
- 쿼리 [-2,5,1] : false
- 쿼리 [-1,1,5] : {1,3,5}, {2}, {4}
- 쿼리 [-1,3,5] : {1,3,5}, {2}, {4}
- 쿼리 [-1,2,5] : {1,2,3,5}, {4}
- 쿼리 [-1,1,2] : {1,2,3,5}, {4}
- 쿼리 [-2,5,4] : false