[Java] 월간 코드 챌린지2 (모두 0으로 만들기)

문제 설명

---

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

• 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

---

제한사항

• a의 길이는 2 이상 300,000 이하입니다.
  • a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
  • a[i]는 i번 정점의 가중치를 의미합니다.
• edges의 행의 개수는 (a의 길이 - 1)입니다.
  • edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
  • edges가 나타내는 그래프는 항상 트리로 주어집니다.

---

입출력 예

aedgesresult

[-5,0,2,1,2]	[[0,1],[3,4],[2,3],[0,3]]	9
[0,1,0]	[[0,1],[1,2]]	-1

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 트리의 모든 정점의 가중치를 0으로 만드는 과정을 나타낸 것입니다.

1. 2번 정점과 3번 정점을 선택하여 2번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
2. 3번 정점과 4번 정점을 선택하여 4번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
3. 0번 정점과 3번 정점을 선택하여 3번 정점은 1 감소시키고, 0번 정점은 1 증가시킵니다. (5번 반복)

• 모든 정점의 가중치를 0으로 만드는 데 필요한 최소 행동 횟수는 9번이므로, 9를 return 해야 합니다.

입출력 예 #2

• 주어진 트리는 모든 정점의 가중치를 0으로 만드는 것이 불가능하므로, -1을 return 해야 합니다.

 

접근 방법

---

1. 가장 먼저 확인해야할 부분은 모두 0으로 만들 수 있는지 아닌지 입니다.

 

 모든 노드의 가중치의 합이 0이라면 모두 0으로 만드는 것이 가능하고, 반대의 경우는 모든 가중치를 0으로 만드는 것이 불가능합니다.

 

2. 어떻게 해야 최소의 횟수로 모든 가중치를 0으로 만들 수 있을까? 

 

 가장 최소의 횟수로 모든 가중치를 0으로 만드려면 반복되는 연산(가중치 교환)과정이 있어서는 안됩니다. 즉 일방향으로 연산을 적용한다면 노드의 어떤 부분부터 시작하더라도 모두 같은 최솟값을 구할 수 있습니다. 

 

 

 노드의 연결 정보는 무조건 트리의 형태로 주어진다는 것을 알 수 있습니다. 즉 어떤 임의의 노드를 루트로 잡고 DFS를 사용하여 자식의 방향으로 향하게 설계 후, 리프(말단)노드로부터 부모 노드의 방향으로 연산을 적용하여 해결할 수 있습니다.

 

소스 코드

---

import java.util.*;

class Solution {
    
    ArrayList<ArrayList<Integer>> info;
    boolean[] visited;
    long[] a;
    long cnt = 0;
    
    void solve(int now){
        
        //부모노드로 올라가지 못하게 방문노드 check
        visited[now] = true;
        
        for(int i=0;i<info.get(now).size();i++){
            int next = info.get(now).get(i);
            if(visited[next] == false){
                solve(next);
                a[now] += a[next];
            }
        }
        //cnt는 연산이 일어나는 횟수
        cnt += Math.abs(a[now]);
    }
    
    
    void makeInfo(int[][] edges){
        
        info = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0;i<this.a.length;i++)
            info.add(new ArrayList<Integer>());
        
        for(int i=0;i<edges.length;i++){
            info.get(edges[i][0]).add(edges[i][1]);
            info.get(edges[i][1]).add(edges[i][0]);
        }
    }
    
    public long solution(int[] a, int[][] edges) {
        
        long sum = 0;
        
        this.a = new long[a.length];
        this.visited = new boolean[a.length];
        
        for(int i=0;i<a.length;i++){
            this.a[i] = a[i];
            sum += this.a[i];
        }
        //합이 0이 아니라면 가중치를 0으로 만들 수 없음
        if(sum != 0)
            return -1;
        
        //인접리스트로 표현
        makeInfo(edges);
        
        solve(0);
        return cnt;
    }
}