[programmers][월간 코드 챌린지 시즌2] 모두 0으로 만들기

문제 : programmers.co.kr/learn/courses/30/lessons/76503#

---

연결된 두 점의 한 쪽은 +1, 다른 한 쪽은 -1을 하면 플마제로이기 때문에 결국 모든 노드의 가중치들의 합은 유지된다.

따라서 모든 노드들의 가중치 합이 0가 되지 않는다면 -1을 반환한다.

모든 노드들의 가중치 합이 0이 아니라면 가중치를 0으로 만드는 것은 가능하다.

 

임의의 노드를 루트노드라 가정하고 해당 노드로 다른 모든 노드들의 가중치를 루트노드로 이동시켜보자.

[그림 1]

[그림 1]은 가중치 0을 가진 노드를 루트노드라 가정하여 다른 노드들의 가중치를 순수하게 옮긴다고 가정했을 때의 이동횟수이다. 예를 들어 3 노드의 가중치를 0 노드로 옮길 때 -1 노드를 거치지만 단순히 거쳐가는 노드로만 사용된다.

총 이동횟수는 3노드 이동 횟수(6) + -1 노드이동횟수 (1) + -2 노드 이동횟수 (4) 로 총 11이다.

 

가중치의 합을 구하는건데 -1 노드를 단순 중간 거점으로 사용하기엔 많은 손해가 있어보인다.

이번엔 중간에 거쳐가는 노드들(서브트리의 루트노드)에서 하위 노드들의 가중치들을 모두 합한 값을 부모노드로 옮겨보자.

[그림 2]

[그림 2]에서는 -1, 3, -2 서브트리의 루트노드인 -1 에서 자식 노드들의 가중치 합을 구한 뒤 이를 부모노드로 이동시켰다.

총 이동횟수는 3 + 2 + 0 = 5이다.

이게 더 효율적이다.

 

즉, dfs로 자식 노드들을 탐색하면서 탐색중인 노드를 루트노드로 하는 서브트리의 합을 갱신하면서 가중치의 절대값을 이동횟수에 더해준다. 

func dfs(index) {
  sum = 가중치[index] + dfs(자식노드)의 합
  answer = answer + |dfs(자식노드)|의 합
  return sum
}

수도코드로 간단히 표현하면 위와 같다.

 

시간복잡도는 모든 노드들을 탐색하는데 드는 시간인 O(N). N = |a|

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C2/%EB%AA%A8%EB%91%90%200%EC%9C%BC%EB%A1%9C%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp