dev_eun

코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 트리이기 때문에 어떠한 노드를 골라도 루트노드가 될 수 있다. 리프 노드부터 시작해서 bottom-up으로 루트까지 올라가면 되겠다고 생각했었다. 그러려면 부모 노드가 누구인지 알아야 하는데, 그렇게 할 필요가 없었다. 자식 노드의 순서가 중요하지 않기 때문에 자식 노드의 수만 세고 있으면 되었던 것. 그래서 리프 노드부터 시작해서 자신과 각 부모 노드의 weight를 수정하는 방식으로 진행했다. 루트(0번 노드)에서 시작하는 dfs, bfs로..