모두 0으로 만들기

• https://programmers.co.kr/learn/courses/30/lessons/76503

문제풀이

DFS로 푸는 문제인데, 상당히 조건이 까다로웠다.
우선, 자바스크립트로 재귀로 풀면 터져버린다. 파이썬의 경우 내부적으로 재귀함수 Limit을 바꿀 수 있지만,
자바스크립트는 불가능한 것 같다.(실행 시킬 때 nodejs의 경우 지정할 수 있는듯?) 그래서 반복문으로 풀어야한다. 또 까다로웠던 점은 숫자의 크기가 커서 BigInt를 사용해서 합을 구해야한다.(안그럼 틀림)

1. 트리로 주어졌으니 임의의 한 점에서 부터 dfs로 탐색 후 리프노드에서부터 가중치를 더한다.

소스코드

function solution(a, edges) {
    let answer = 0n;
    const adj = Array.from(Array(a.length), () => []);
    const visited = Array(a.length).fill(false);
    edges.forEach(e => {
        const [u, v] = e;
        adj[u].push(v);
        adj[v].push(u);
    });
    if(a.reduce((acc,val) => acc+val, 0) !== 0) return -1;
    const arr = [[0, null]];
    while(arr.length){
        const [start, parent] = arr.pop();
        if(visited[start]){
            answer += BigInt(Math.abs(Number(a[start])));
            a[parent] += a[start];
            a[start] = 0;
            continue;
        }
        visited[start] = true;
        arr.push([start, parent]);
        for(const v of adj[start]){
            if(visited[v]) continue;
            arr.push([v, start]);
        }
    }
    return Number(answer);
}