문제 - 모두 0으로 만들기

문제접근

1.모든 점들의 가중치들을 0으로 만들기 위해서는 가중치의 합이 0이여야 가능하기 때문에 가중치의 합이 0이 아닌 경우에는 불가능(-1)출력
2.트리이므로 dfs로 0부터 탐색 (어느 노드부터 시작하든 상관없다)
3.탐색하면서 리프노드부터 부모노드에 가중치를 합산

• 참고

소스코드

import java.util.*;

class Solution {
    ArrayList<Integer> graph[];
    long answer = 0;
    boolean visited[];
    long atmp[];
    public long solution(int[] a, int[][] edges) {
        
        //안되는 경우 : 가중치의 합이 0이 안되는 경우
        atmp = new long[a.length];
        for(int i=0;i<a.length;i++)
        {
            atmp[i] = a[i];
            answer+=atmp[i];
        }
        if(answer != 0) return -1;
        //되는 경우 : 횟수 체크
        graph = new ArrayList[a.length];
        visited = new boolean[a.length];
        
        for(int i=0;i<a.length;i++)
        {
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges)
        {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        dfs(0);
        
        return answer;
    }
    
    public long dfs(int now)
    {
        visited[now] = true;
        
        for(int i=0;i<graph[now].size();i++)
        {
            int next = graph[now].get(i);
            if(visited[next]) continue;
            atmp[now] += dfs(next);
        }
        
        answer += Math.abs(atmp[now]);
        return atmp[now];
    }
}

위상정렬 알고리즘 이용

import java.util.*;

class Solution {
    ArrayList<Integer> graph[];
    long answer = 0;
    boolean visited[];
    long atmp[];
    public long solution(int[] a, int[][] edges) {
        int len = a.length;
        //안되는 경우 : 가중치의 합이 0이 안되는 경우
        atmp = new long[len];
        for(int i=0;i<len;i++)
        {
            atmp[i] = a[i];
            answer+=atmp[i];
        }
        if(answer != 0) return -1;
        //되는 경우 : 횟수 체크
        graph = new ArrayList[len];
        visited = new boolean[len];
        //진입간선
        long indegree[] = new long[len];
        
        for(int i=0;i<len;i++)
        {
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge : edges)
        {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
            indegree[edge[0]]++;
            indegree[edge[1]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        //리프노드들을 큐에 저장
        for(int i=0;i<len;i++)
        {
            if(indegree[i]==1){
                q.offer(i);
                
            }
                
        }
        
        while(!q.isEmpty())
        {
            int now = q.poll();
            visited[now] = true;
            
            for(int next : graph[now])
            {
                if(visited[next]) continue;
                
                atmp[next] += atmp[now];
                answer+=Math.abs(atmp[now]);
                atmp[now] =0;
                indegree[next]--;
                if(indegree[next] == 1)
                    q.offer(next);
            }
        }
        return answer;
    }
    
    
}