기록

문제https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한programmers.co.kr풀이각 leaf node에서 가중치를 부모 노드로 옮긴다.이 과정을 leaf 노드가 사라질 때까지 반복한다. 시간초과dfs 나 bfs를 이용해서 모든 노드를 탐색하도록 했으나, 시간초과로 대부분의 테스트 케이스에서 통과하지 못했다. leaf node를 제거하면, 그 부모가 leaf node 후보가 되므로, 부모가 가진 간선개수를 이용해서 다음에 ..