[프로그래머스] 모두 0으로 만들기

코딩테스트 연습 - 모두 0으로 만들기

 

트리이기 때문에 어떠한 노드를 골라도 루트노드가 될 수 있다.

리프 노드부터 시작해서 bottom-up으로 루트까지 올라가면 되겠다고 생각했었다. 그러려면 부모 노드가 누구인지 알아야 하는데, 그렇게 할 필요가 없었다.

자식 노드의 순서가 중요하지 않기 때문에 자식 노드의 수만 세고 있으면 되었던 것.

 

그래서 리프 노드부터 시작해서 자신과 각 부모 노드의 weight를 수정하는 방식으로 진행했다.

 

루트(0번 노드)에서 시작하는 dfs, bfs로 시도해봤지만 나는 모두 실패...

다른 사람들의 풀이에는 dfs로 푼 것도 꽤 있는 것 같다.

 

c++

eun-seong/Documents

 

js

스택으로 dfs할 때 루트 노드부터 task를 수행하는 것이 아니라 리프 노드부터 수행

eun-seong/Documents