BOJ 13306 - 트리 (https://www.acmicpc.net/problem/13306)
발상의 전환이 살짝 필요한 문제였다.
쿼리를 입력받은 순서대로 처리해야 된다고 생각했는데, 그렇지 않은 경우도 있다는걸 알게된 시간이었다.
풀기 위해 알아야 할 것
일단 Union-Find (Disjoint Set) 를 알아야한다.
그리고 문제를 매우 잘 읽어봐야 한다. 입력 설명 중간에, 아래와 같은 문장이 나온다.
다음 (N-1)+Q개의 줄 중에서 N-1개는 (1)의 형태로, Q개는 (2)의 형태로 주어진다.
N이 정점의 개수라는걸 생각했을 때, (1)의 형태가 N-1개만큼 주어진다는 것은 결국 모든 간선은 다 끊어진다 라는 것을 의미한다.
푸는 방법
처음에는 내 스스로 실마리를 찾지 못했으나, 아는 동생과 함께 풀던 중에 아래와 같은 아이디어를 전수 받았고 그것을 토대로 구현해봤다.
1) 우선 간선 정보를 입력 받아 정점들의 부모를 보관하는 배열을 구성하고, 이후 입력 받게 되는 쿼리들을 모두 스택에 저장한다.
-> 이 때, 연산을 처리할 때 사용할 Union-Find용 배열을 하나 만들어둔다.
2) 쿼리를 모두 스택에 저장했으면 이제 그 것들을 하나씩 꺼내서 처리하면 된다. 단, (2)의 형태에 해당하는 연산을 반대로 처리한다.
-> 반대로 처리한다는 것은, 입력 받은 a 정점과 a 정점의 부모를 연결하는 연산을 수행하는 것이다.
트리를 만들어서 일일히 하나씩 끊어보고 이어져있는지 순회하는게 아니라, 서로 연결되어 있지 않은 상태의 정점들을 각각 하나의 Union으로 간주하고 여기에 Union, Find 연산을 해주는 것이 이 문제의 해법이다.
예제 입력 1번의 쿼리를 위 방법으로 수행해보자.
- 예제 입력 1번 트리 모양 (초기 상태)
초기 상태는 이렇고, 이후 입력 받은 쿼리 5개를 스택에 넣은 뒤 하나씩 꺼내보자.
스택 상태
[0, 2] <- Top
[1, 1, 2]
[1, 2, 3]
[0, 3]
[1, 2, 3] <- Bottom
Union 상태
union[1] = 1, union[2] = 2, union[3] = 3
먼저 [0, 2]를 꺼낸다. (1)의 형태로 주어진 쿼리이며, 2번 정점의 부모는 1이다. 따라서 union(1, 2)로 두 정점을 묶어준다.
스택 상태
[1, 1, 2] <- Top
[1, 2, 3]
[0, 3]
[1, 2, 3] <- Bottom
Union 상태
union[1] = 1, union[2] = 1, union[3] = 3
이제 [1, 1, 2]를 꺼낸다. (2)의 형태로 주어진 쿼리이며, find(1)과 find(2)가 동일한 정점을 가리키는지 확인하면 된다. 바로 직전의 쿼리에서 두 정점을 묶어줬기 때문에 이 쿼리의 처리 결과는 YES다.
그 다음으로 [1, 2, 3]을 꺼낸다. find(1)과 find(3)을 해본 결과 3번 정점은 다른 Union에 속해있기 때문에 이 쿼리의 처리 결과는 NO다.
스택 상태
[0, 3] <- Top
[1, 2, 3] <- Bottom
Union 상태
union[1] = 1, union[2] = 1, union[3] = 3
이번에는 [0, 3]을 꺼낸다. (1)의 형태로 주어진 쿼리이며, 3번 정점의 부모는 1이다. 따라서 union(1, 3)으로 두 정점을 묶어준다. 이제 모든 정점이 같은 Union에 속하게 되었다.
스택 상태
[1, 2, 3] <- Top, Bottom
Union 상태
union[1] = 1, union[2] = 1, union[3] = 1
마지막으로 [1, 2, 3]을 꺼낸다. (2)의 형태로 주어진 쿼리이며, find(2)와 find(3)의 결과는 동일하게 1번 정점을 가리킨다. 따라서 이 쿼리의 처리 결과는 YES다.
이런 식으로 처리를 다 했으면 그 결과를 출력해주기만 하면 되는데, 여기서 주의해야할 점은 쿼리를 저장했을 때와 마찬가지로 스택을 사용해야 된다는 것이다. 쿼리를 맨 밑에서 하나씩 올라오면서 처리 한 것이기 때문에 스택에 한번 더 넣고 빼야 순서가 맞기 때문이다.
아니면 전부 배열에 따로 저장하고 맨끝 index부터 순회해서 출력해줘도 무방하다.