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

- 링크 : https://programmers.co.kr/learn/courses/30/lessons/76503

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

 

- 참고 링크 : https://dev-note-97.tistory.com/263

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

 

- 풀이

 : dfs 진행 후 역순으로 계산하며 (dfs 의 함수 호출 스택은 쌓으면 역으로 풀리는 성질 이용)

 : 각 단계에서 더해질 값을 계산

 

import java.util.*;

class Solution {
    boolean[] visited;
    List<Integer>[] edgesList;
    long[] edgeWeights;
    long sum;
    
    public long solution(int[] a, int[][] edges) {
        int edgeLen = a.length;
        for (int weight : a) {
            sum += weight;
        }
        if (sum != 0) {
            return -1;
        }
        visited = new boolean[edgeLen];
        edgeWeights = new long[edgeLen];
        edgesList = new ArrayList[edgeLen];
        for (int i=0; i<edgeLen; i++) {
            edgesList[i] = new ArrayList<Integer>();
            edgeWeights[i] = a[i];
        }
        
        for (int[] edge: edges) {
            int v1 = edge[0];
            int v2 = edge[1];
            
            edgesList[v1].add(v2);
            edgesList[v2].add(v1);
        }
        
        dfs(0);
        
        return sum;
    }
    
    public long dfs(int currV) {
        visited[currV] = true;
        
        for (int i=0; i<edgesList[currV].size(); i++) {
            int nextV = edgesList[currV].get(i);
            if (!visited[nextV]) {
                edgeWeights[currV] += dfs(nextV);
            }
        }
        
        sum += Math.abs(edgeWeights[currV]);
        
        return edgeWeights[currV];
    }
}