프로그래머스 [Lv. 3] 모두 0으로 만들기 {언어 : JavaScript} [다시 풀어 보기] [6, 7, 8, 15, 16, 17번 테스트 케이스]

문제 링크

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

프로그래머스

정답 코드

function solution(a, edges) {
    const n = a.length;
    const adjL = Array.from({ length: n }, () => []);

    // 모든 숫자를 BigInt로 변환
    a = a.map(BigInt);

    for (const [start, to] of edges) {
        adjL[start].push(to);
        adjL[to].push(start);
    }

    let result = BigInt(0);
    const stack = [{ node: 0, parent: -1 }];
    const visited = Array(n).fill(false);

    while (stack.length > 0) {
        const { node, parent } = stack.pop();
        
        if (!visited[node]) {
            visited[node] = true;
            stack.push({ node, parent: parent, visiting: true });
            for (const neighbor of adjL[node]) {
                if (!visited[neighbor]) {
                    stack.push({ node: neighbor, parent: node });
                }
            }
        } else {
            if (parent !== -1) {
                result += a[node] < 0n ? -a[node] : a[node];
                a[parent] += a[node];
                a[node] = BigInt(0);
            }
        }
    }

    return a[0] === BigInt(0) ? result : -1;
}

풀이 방법

1. 초기화
   • n: 노드의 개수를 저장한다.
   • adjL: 각 노드의 이웃 노드들을 저장하는 인접 리스트
   • a: 각 노드의 값을 BigInt로 변환한다.
2. 인접 리스트 생성
   • 주어진 edges를 사용해 인접 리스트를 채웁니다. 각 간선은 양방향이므로 양쪽에 서로를 추가한다.
3. DFS를 위한 스택과 방문 배열 초기화
   • result: 최종 이동 횟수를 저장한다.
   • stack: DFS를 위한 스택으로 초기에는 루트 노드(0)와 부모 노드(-1)를 저장한다.
   • visited: 각 노드의 방문 여부를 기록하는 배열
4. 반복적 DFS
   • 스택이 비어있을 때까지 반복한다.
   • 스택에서 현재 노드와 부모 노드를 꺼낸다.
   • 노드가 방문되지 않았다면 방문 처리하고, 이웃 노드들을 스택에 추가한다.
   • 노드가 이미 방문된 경우, 부모 노드로 값을 이동시키고 이동 횟수를 result에 더한다.
5. 결과 반환
   • 루트 노드의 값이 0이면 result를 반환합니다. 그렇지 않으면 -1을 반환한다.

느낀점

• dfs로 바텀업 방식까지 떠올리긴 했으나 아래와 같은 문제를 해결하는데 어려움이 있었다.
• 그리고 위의 방식이 더 빠르다는 것을 알았다.
  • Array.from({ length: n }, () => []); - 빠름
  • Array(n).fill().map(() => []);

문제 발생

• 런타임에러
  • 6번 7번 8번 15번 16번 17번 => 재귀의 깊이 문제로 예상
  • 재귀가 아닌 while로 문제 해결
• 8번 실패
  • 정수 범위를 넘어서 생기는 문제로 예상
  • JavaScript의 Number 타입은 64비트 부동소수점 숫자 형식을 사용하기 때문에, 안전하게 정수를 표현할 수 있는 최대 범위는 -(2^53 - 1)에서 2^53 - 1까지이다. 
  • 만약 문제에서 주어지는 값들이 이 범위를 초과한다면, BigInt를 사용해야 한다. BigInt는 임의의 큰 정수를 안전하게 다룰 수 있도록 지원한다.