leechhe   1년 전

일단 각 노드별 인접 리스트를 만들고

parent 배열에 부모 노드를 저장합니다. parent[root] == 0 입니다.

그리고 leaf 노드부터 위로 올라가며 자신의 자식 수와 갖고 있는 구슬의 수를 더해서 저장합니다. child 배열엔 각 노드 아래있는 모든 자식 수가 저장이 되겠죠.

ballsum배열에도 각 노드 아래에 모든 구슬의 수가 저장이 됩니다.

그리고 루트노드부터 BFS로 탐색을 시작하는데, 각 노드 아래 모든 구슬의 수와 (자식의 수+1)의 차이가 이동한 구슬의 수가 되므로 절댓값을 각각 더했습니다.

예제는 다 맞게 나오고 나름 테스트 케이스를 만들었는데 오답이라고 하네요 ㅠㅠ 알려주시면 감사하겠습니다.

댓글을 작성하려면 로그인해야 합니다.