[프로그래머스] 월간 코드 챌린지 - 모두 0으로 만들기

문제

월간 코드 챌린지 시즌 2 - 모두 0으로 만들기

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

 

 

풀이

설명

트리의 모든 점들의 가중치를 0으로 만들 때 필요한 최소 횟수를 구하는 문제입니다.

 

그래프 탐색을 통해 가중치와 연산 횟수를 업데이트해야 합니다.

연산 횟수는 가중치의 절댓값을 더해주면 됩니다.

 

문제를 풀 때 유의할 점이 두 가지 있습니다.

1. dfs 재귀 방식으로 풀 경우, 재귀 호출 깊이가 깊어져 스택 오버플로우가 발생할 수 있습니다.
2. 가중치 값이 매우 커 일반적인 넘버타입으로는 연산 시 허용 범위를 넘을 수 있습니다.

 

그래서 저는 비재귀 방식의 dfs를 사용하고, BigInt로 값을 저장했습니다.

 

예시 코드

function solution(a, edges) {
    const n = a.length;
    const graph = Array.from({ length: n }, () => []);
    let totalWeight = a.reduce((sum, val) => sum + BigInt(val), BigInt(0));
    let totalMoves = BigInt(0);

    if (totalWeight !== BigInt(0)) return -1;

    edges.forEach(([u, v]) => {
        graph[u].push(v);
        graph[v].push(u);
    });

    const stack = [];
    const parents = Array(n).fill(-1);
    const order = [];
    stack.push(0);

    while (stack.length) {
        const node = stack.pop();
        order.push(node);

        const neighbors = graph[node];
        for (const neighbor of neighbors) {
            if (parents[node] === neighbor) continue;
            parents[neighbor] = node;
            stack.push(neighbor);
        }
    }

    for (let i = order.length - 1; i >= 0; i--) {
        const node = order[i];
        let excess = BigInt(a[node]);

        for (const neighbor of graph[node]) {
            if (parents[node] === neighbor) continue;
            excess += BigInt(a[neighbor]);
        }

        totalMoves += BigInt(Math.abs(Number(excess)));
        a[node] = Number(excess);
    }

    return totalMoves;
}