[BOJ 23844] 백준 23844번 - 트리 정리하기

1. 문제Permalink

$23844$. 트리 정리하기 (INU 코드페스티벌 2021 Open Contest D번)

백준 23844번 - 트리 정리하기 (https://www.acmicpc.net/problem/23844)

2. 풀이Permalink

제일 깊은 $depth$부터, 해당 $depth$의 노드 개수가 $a$개이면, $max(0, a - K)$개만큼 제거한다. 이때, 자식노드의 총 개수가 적은 순서대로 제거한다.

다음 그림과 같이 트리가 구성되어 있고 $K=1$이라고 가정하자.

• 제일 얕은 $depth$부터 제거할 경우

$depth=1$에서 node를 한 개 제거해야 하는데 subtree1의 총 노드 개수는 $3$, subtree2의 총 노드 개수는 $4$이므로 subtree1이 제거된다. 그렇게 되면 subtree2의 $depth=2$에서 $2$개를 추가로 더 제거하여 남는 노드의 개수가 $3$개가 된다.

그런데 최대한 많은 노드를 남기기 위해서는 $depth=1$에서 subtree1을 남겨서 답이 $4$가 나와야 한다. 따라서 제일 얕은 $depth$부터 제거하는 방식은 몇몇 경우에서 답에 도달할 수 없어 적절한 방법이 아니다.

• 제일 깊은 $depth$부터 제거할 경우

$depth=3$에서 node $1$개 성립. $depth=2$에서 node를 $3$개 제거해야 하는데, 왼쪽 노드는 총 노드 개수가 $2$개여서 오른쪽 노드 $3$개가 제거된다. 따라서 $depth=3$에서의 최적의 결과를 계속 이어받아 최적을 유지할 수 있다. $depth=1$에서도 마찬가지의 이유로 오른쪽 노드가 제거되고 최종적으로 왼쪽 노드 $4$개만 남아 답이 $4$가 된다.

DFS를 돌려서$(root=1)$ 각 노드의 $depth$와 자식 노드의 총 개수(본인 포함), 부모 노드의 번호(후에 설명)을 알아낸다. 각각의 $depth$에서 $K$개만 남기고 나머지 노드들을 자식 노드의 총 개수가 적은 순서대로 제거해야 한다. 나는 priority queue를 사용하였는데, 그냥 정렬하고 제거해도 상관없을 것 같다. (과정 중에 값이 변화하지 않으므로)

제거된 노드의 총 개수를 구하기 위해서 노드를 제거할 때, 그 노드의 자식 노드의 총 개수만큼의 값을 저장해야 한다. (코드 66줄) 이때, 제거되는 노드의 상위 노드에 개수가 그대로 남아있으면 나중에 중복 제거가 일어날 수 있으므로 그 상위노드의 개수 또한 변화시켜주어야 한다.

원래는 해당 노드의 바로 위의 상위노드 뿐만 아니라 모든 상위노드의 값을 변화시켜야 한다. 이는 너무 오버헤드가 심한 작업이므로, ch_Cnt 배열을 따로 만들어서 원래 Cnt값과 변화한 현재 Cnt값을 분리시킨다.

그리고 어떤 노드가 제거되면 그 노드의 원래 자식 노드의 총 개수만큼 바로 위 상위 노드의 개수에서 뺀다. (코드 67줄) 이렇게 하면 $depth$가 $1$씩 감소하므로 값을 한 단계씩 바꾸면서 문제없이 이어갈 수 있다. (이를 위해서 DFS를 돌 때, 각 노드의 Parent node를 저장했다.)

3. 채점 결과Permalink

4. 회고Permalink

$N$의 최댓값을 잘못 체크하여 RTE를 받았다. 또한, 상위노드의 개수 변화 과정을 잘못 구현하여 WA를 받았다.

5. 코드Permalink