[JS] 모두 0으로 만들기

 

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

프로그래머스

 

 

 

문제풀이는 후위탐색을 활용하면 된다.

 

 

트리의 뿌리노드부터 루트 노드까지 값을 전달해준다.. 라는 생각을 하면 된다.

 

이때 굳이 양수가 아니라 음수가 나오더라도 0이 되도록 음수를 전달해도 된다는 개념으로 접근하면 된다.

 

 

따라서 재귀함수를 활용하여 뿌리노드부터 0으로 만들어가며 남은 값들을 부모노드로 전달해주었고 옮긴 만큼의 값을 저장했다.

function solution(a, edges) {
  const tree = [...Array(a.length)].map((_) => []);
  for (const [s, e] of edges) {
    tree[s].push(e);
    tree[e].push(s);
  }

  let ret = 0;
  const dfs = (node, parent) => {
    let val = 0;

    for (const nxNode of tree[node].filter((v) => v !== parent)) {
      val += dfs(nxNode, node);
    }

    val += a[node];
    ret += Math.abs(val);
    return val;
  };

  ret = dfs(0) ? -1 : ret;
  return ret;
}

 

 

 

그런데 런타임 에러가 나오는 테스트 케이스들이 있었다...

 

a의 길이가 300,000이다.. 아마 재귀함수 깊이를 넘어가서 에러가 생기는 것같다.

 

후위탐색을 스택을 활용해서 구현하려면 스택에 노드를 두번 넣는 과정이 필요하다.

 

우선 뿌리노드를 찾고 -> 노드를 재방문 해야하는 과정이 필요하기 때문이다.

 

 

이렇게 해결했는데 8번 테스트케이스를 넘기지 못했다. 문제를 다시보면 a의 모든 수가 1,000,000이란 조건이 붙어있다. 설마 해서 값을 BigInt로 설정해서 코드를 다시 짰더니 해결되었다.

 

function solution(a, edges) {
    a = a.map(v => BigInt(v))
    const tree = [...Array(a.length)].map(_=>[])
    for (const [s,e] of edges) {
        tree[s].push(e)
        tree[e].push(s)
    }
    
    let ret = 0n
    const stk = [[0,0]]
    const visited = Array(a.length).fill(false)
    
    while(stk.length){
        const [node,parent] = stk.pop()
        let val = 0
        if(!visited[node]){
            stk.push([node,parent])
            for (const nxNode of tree[node].filter(v=>v!==parent)){
                stk.push([nxNode,node])
            }
            visited[node] = true
            continue
        }
       
        ret += a[node] > 0 ? a[node] : -a[node]
        a[parent] += a[node]
    }
    
    ret = a[0] ? -1 : ret
    return ret
}

 

 

 

뭔가 문제자체는 어렵지 않은데 재귀제한 , BigInt 등 신경써야 할 부분이 많아 까다로운 문제였다.