백준 23844 - 트리 정리하기 - WhiteHyun's Develop Blog

동빈이가 사는 나라의 나무들은 트리 모양을 하고 있다.

다가오는 크리스마스를 기념해서, 동빈이는 나무를 다듬어서 집에 트리를 장식하기로 했다.

동빈이가 가지고 있는 트리는 N개의 노드들이 N-1개의 간선으로 연결되어 있다. 각 노드들은 1~N까지의 번호가 정해져 있고, 루트 노드의 번호는 1이다.

트리에서 루트 노드의 레벨은 0이고 아래로 갈수록 1씩 증가한다. 동빈이는 모든 노드에 장식을 달고 싶었지만, 트리의 두께가 K를 넘으면 집에 들어가지 않는다.

이때 트리의 두께란, 같은 레벨에 있는 노드의 개수 중 최댓값이다.

결국, 일부 노드를 제거해 트리의 두께가 K이하가 되도록 만들어야 한다. 트리를 다듬을 때 부모 노드를 제거하면 모든 자식 노드도 제거된다.

되도록 많은 장식을 달고 싶은 동빈이는 최대한 많은 노드를 남기려 한다. 여러분이 동빈이를 도와주자.

첫째 줄에 정점의 개수 N과 레벨 당 남길 수 있는 노드의 개수 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N)

다음 N-1개의 줄에 걸쳐, 두 정수 a_i, b_i 가 주어진다. 이는 a_i번 노드와 b_i번 노드가 간선으로 연결되어 있다는 의미이다. (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i)

최대한 많은 노드를 남기고 트리를 정리했을 때 남은 노드의 개수를 출력하시오.

문제에 주어진 트리는 입력에 따라 부모-자식노드 관계로 설정되기 때문에 부모에서 손자노드를 만들 수 없다. 따라서 다음의 트리는 성립하지 않는다.

성립되지않는 노드

결국 해당 문제의 트리는 다음과 같은 트리의 형태가 될 것이다. 특정 LEVEL이 남길 수 있는 노드 K에 대하여 트리를 잘라보자.

성립되는노드

특정 Level이 남길 수 있는 노드 K보다 큰 경우, 그 레벨에서는 최대 K개 까지 밖에 가질 수가 없다. 위 그림에서 K가 2일 경우, Level 2에서 맨 오른쪽 두 개의 노드와 Level 3 중 노드 하나를 삭제하면 최대의 노드를 가질 수 있을 것이다.

그 밖에 그림에서 Level 0나 Level 1과 같이 K 이하인 경우에는 각 레벨의 노드 개수만 세어주면 된다.

삭제노드

각 레벨 별 노드의 개수를 카운트 해주는 리스트를 N의 크기만큼 생성한다.(입력받은 N, K에 대해서 최대 만들어질 수 있는 레벨은 0~N-1이다)
노드간 관계를 입력받을 수 있는 리스트를 N+1의 크기에 빈 리스트로 초기화한다.

N만큼 리스트를 초기화해도 되나, 노드의 인덱스를 편하게 다루기 위해 N+1의 크기로 초기화했다.
N-1만큼 반복하여 두 노드를 입력받을 때 각 노드의 번호를 인덱스로 하여 연결 관계를 추가한다. 예를 들어, level 1에 2, 3, 4번 노드가 있고, level 2에 5번노드가 2번노드와 부모관계를 맺고있다면 리스트는 다음과 같이 저장된다.
level 0부터 시작하여 DFS로 level별 노드를 카운트해준다. 만약 특정 레벨에서 K개 이상이라면 카운트 하지 않게 구현한다.

백준 23844 - 트리 정리하기