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

😀주요 포인트

1. JS는 Maximum Call Stack이 엄격하기 때문에, DFS 재귀 스택이 버티질 못하는 문제로 Stack의 구조로 풀이해야함

2. 해당 문제는 입출력 값이 매우 커질 수 있기 때문에 BigInt를 사용해야함

큰 도움이 된 longroadhome님의 Velog

😁코드

function solution(a, edges) {
    // 모든 수의 합이 0이 아니라면 모두 0으로 만들기 불가
    if(a.reduce((acc, cur) => acc + cur, 0) !== 0) return -1

    const graph = Array.from(Array(a.length), () => []);
    const visited = Array(a.length).fill(false);
    // 입 출력 예시의 복잡성으로 BigInt 사용해야함
    let answer = 0n;

    // 간선 생성
    for(const [from, to] of edges) {
        graph[from].push(to)
        graph[to].push(from)
    }
	// dfs를 stack으로 대체하려면 부모 요소를 동시에 알고있어야 함
    const stack = [[0, -1]];
    while (stack.length) {
        const [child, parent] = stack.pop();
        if(visited[child]) {
            // 부모에게 현재 수를 모두 합하여 최종적으로 0의 인덱스에 최종합
            a[parent] += a[child]
            // 모든 수를 빼내기 위해 그 간선이 갖고있던 수 만큼이 필요
            answer += BigInt(Math.abs(a[child]));
            continue
        }
        stack.push([child, parent])
        visited[child] = true;
        for (const next of graph[child]) {
            if (visited[next]) continue;
            stack.push([next, child]);
        }
    }
    return a[0] === 0 ? Number(answer.toString()) : -1;
}