[Programmers] 모두 0으로 만들기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/76503

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

주어진 자료형은 int지만 더하는 과정에서 오버플로우가 발생할 수 있으므로 long long으로 변환해야 하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 가중치의 합산이 0이 아니라면 가중치를 모두 0으로 만드는 것이 불가능합니다.

1.1 따라서 0이 아닐 경우 -1을 반환해줍니다.

2. 트리는 모든 노드가 연결되어있으므로 어느 노드를 루트로 잡아도 상관이 없습니다. 따라서 간단하게 0을 루트로 해서 DFS를 돌립니다.

2.1 DFS를 돌리면서 각 가중치를 업데이트 합니다. (결국 두 노드의 가중치를 합산한 값이 업데이트하는 최소 횟수)

3. 2번에서 구한 가중치의 합산을 반환해줍니다.

 

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~