백준 17469 자바 - 트리의 색깔과 쿼리 (BOJ 17469 JAVA)

[ 백준 17469 ]

[ 코드 (깃헙) ]

 

  트리의 부모를 알려주고, 주어진 쿼리를 해결해야 한다. 쿼리는 '1 a'와 같이 들어오면 간선 제거, '2 a'와 같이 들어오면 a에서 갈 수 있는 정점들에 포함된 색깔 종류의 개수를 출력해야 한다.

 

  당연히 매번 쿼리를 진행하고 bfs나 dfs로 갈 수 있는 경로를 찾고 또 해당 노드들에 존재하는 색깔 종류를 셀 순 없다(시간초과). 그럼 일단 각 부분들을 뭘 이용해 구할 수 있을지 확인해보자. 

1. 갈 수 있는 정점들 확인 : union-find를 사용한 그룹짓기

 

2. 각 그룹에 포함된 색깔 종류의 개수 : HashSet을 사용하면 애초에 동일한 색깔이 중복해서 안들어가니, 해당 set의 size()만 확인하면 해당 그룹에 포함된 색깔 종류의 개수를 알 수 있다.

 

3. 그룹과 그룹이 합쳐지는 경우 색깔 종류의 개수는 어떻게 합칠 것인가? : A 그룹과 B 그룹을 합칠 경우, 한쪽 그룹의 HashSet을 다른 쪽 그룹에 addAll 해버리면 된다. (A가 {1,2,3}, B가 {2,3,4} 였다면 A에 B를 addAll하면 {1,2,3,4}가 된다.) 추가로 더 큰 그룹에 더 작은 그룹을 합쳐버리는게 더 시간복잡도 면에서 이득이다(이 부분은 union-find 구현 시 처리해주면 된다. 위 코드의 경우 parents 배열이 음수라면 해당 트리에 포함된 '-그룹의 갯수'를 뜻한다(rank). 따라서 union 부분에서 h와 l을 둬서 더 rank가 높은쪽에 rank가 낮은쪽을 addAll 한다.

 

4. union-find로 합칠 순 있어도, 간선을 제거해서 그룹을 끊기는 어렵다. : 쿼리를 순서대로 진행하면 'edge를 제거하면서 그룹의 색깔 개수 확인'인데, 미리 쿼리에 존재하는 edge 제거 쿼리 부분을 모두 처리해서 쿼리에서 제거되지 않은 edge만 남긴 상태로 쿼리를 역순으로 진행하면 'edge를 연결하면서 그룹의 색깔 개수 확인'으로 변경되게 된다.

 

 

로직을 정리하면 다음과 같다.

 

A. 쿼리에 존재하는 간선을 미리 제거한다. 쿼리에 없는 간선만 연결해두면 된다. 이 문제의 경우 '1번 쿼리는 N-1개'라는 조건이 있고, 트리는 항상 N-1개의 간선을 가지므로 단순히 간선을 아무것도 연결하지 않은채로 시작하면 된다.

 

B. union-find와 HashSet을 사용해 쿼리를 역순으로 진행하면서 출력할 내용을 어딘가에 역순으로 쌓아둔다.

 

C. 쌓아둔 답변을 원래 출력해야할 순서대로 출력한다.