문제 설명
정점의 개수 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 : 한 원소가 어느 집합에 포함되어 있는지 판단합니다.
분리 집합은 트리와 루트노드를 이용해 표현됩니다. 아래 그림 예시를 통해 확인할 수 있습니다.
초기 상태는 다음과 같이 정의됩니다. 각각의 정점번호는 1~7이며 각 정점은 서로 다른 집합에 포함되어 있고, 집합의 번호는 정점의 번호와 동일한 상태입니다.
이후 Union 2, 5를 진행한 상황을 가정합니다. 2번 정점과 5번 정점이 서로 연결되면 동일한 집합으로 분류됩니다. 이때 집합의 번호를 2번 또는 5번으로 병합할 수 있는데, 지금의 문제상황에서는 더 낮은 집합 번호로 병합을 진행한다고 가정합니다.
Union 4, 7도 동일하게 연산을 진행하면 아래 그림과 같이 집합 번호가 갱신됩니다.
Find 연산은 집합 번호를 반환하는 연산이며, 대체로 두 정점이 동일한 집합에 포함되어 있는지를 확인하는 데에 사용됩니다. "Find 7" 연산의 경우 4를 반환하게 됩니다.
Union 1, 7 연산을 진행합니다. 7번 정점은 이미 4번 집합에 포함되어 있는 상황이기 때문에 1번 집합과 4번 집합을 병합하는 연산이 진행됩니다. 앞선 상황과 동일하게 집합 번호가 더 작은 1번 집합으로 병합하는 과정에서 4번 정점과 7번 정점이 모두 1번 집합으로 포함됩니다.
비슷하게 Union 5, 3을 진행하면 다음과 같이 3번 정점의 집합 번호가 갱신됩니다.
해당하는 상황에서 3번 정점이 속해 있는 집합 번호는 2입니다.
이후 Union 5, 7 연산 상황을 가정합니다. 5번 정점은 2번 집합, 7번 정점은 1번 집합에 포함되어 있었기 때문에 1번 집합과 2번 집합을 병합합니다. 원래 2번 집합에 포함되어 있던 2, 3, 5번 정점을 1번 집합으로 포함합니다.
이후 다시 3번 정점에 속해있는 집합 번호를 살피면 1번 집합에 포함되어 있음을 확인할 수 있습니다.
이러한 유니온 파인드 알고리즘은 Union 연산 시 어느 집합을 병합시킬지에 대한 기준인 Union By Rank, Union By Size 등의 방법과 Find를 하면서 집합 번호를 갱신시키는 Path Compression 방법을 통해 최적화가 가능합니다.
최적화되지 않은 유니온 파인드 알고리즘은 쿼리 당 O(N)의 시간복잡도가 소요되지만, Union By Rank/Size + Path Compression 최적화를 모두 적용한다면 쿼리 당 시간복잡도가 역아커만함수이며 이는 일 때 함숫값이 5로 거의 상수함수와 같습니다.
제한 사항
n은 주어지는 정점의 개수이며 10,000 이하의 자연수입니다. 각 정점은 1 이상 n 이하의 정점번호를 가집니다.
queries는 아래와 같은 쿼리 정보를 10,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