문제

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

입력으로 가중치와 트리가 주어진다. 간선으로 연결된 임의의 두 노드를 골라 한쪽은 1을 더하고 한쪽은 1을 빼는 연산을 통해 가중치를 모두 0으로 만들어야 한다. 만약 가중치를 모두 0으로 만드는게 불가능하다면 -1을 출력하고, 가능하다면 연산 횟수를 출력하는 문제다.

첫번째 접근법

처음으로 접근한 방법은 이렇다.

그래프 graph 를 인접리스트로 입력받는다.
가중치 a를 배열로 입력받는다.

while(true){
  노드가 한개만 연결 된곳을 찾는다.
  해당 노드의 연결된곳과 연산을 실시해 0으로 만든다.
  해당 노드는 0으로 바뀌었으므로, 그래프에서 제거한다.
  
  if ( 그래프에 노드가 두개만 남으면 ) {
    if ( 두개의 노드를 합친값이 0 이면 ) {
      result = result + |둘중 한개의 노드|
    }else {
      result = -1;
    }   
    break;
  }
}

그래프에서 n번의 탐색으로 한개만 연결된곳을 찾는 과정을 n!번 반복하므로 무조건 시간초과가 뜬다.
그래서 처음에 제출했을땐 1,2개를 제외한 모든 결과가 시간초과가 나왔다.

두번째 접근법

그래서 시간초과를 줄이고자 dfs로 접근했다.

그래프를 인접리스트로 입력받는다.
가중치 a를 배열로 입력받는다.

function dfs(이전노드, 현재노드) {
  for ( 다음노드 of 그래프[현재노드] ) {
    만약 ( 다음노드 == 이전노드 ) continue
   	dfs ( 현재노드, 다음노드 )
  }
  
  a[이전노드] = a[이전노드] + a[현재노드]
  결과 = 결과 + |a[현재노드]|
}
  
dfs(-1, 0)
  
a[0] == 0이라면 결과를 출력하고, 아니라면 -1을 출력한다.

처음에는 그래프의 루트가 없다고 생각해 위상정렬 후에 탐색을 시작해야 한다고 생각했다.
하지만 루트가 어디든지 상관없다. 결국 트리로 연결돼있다고 문제에 적혀있기 때문이다.

그리고 dfs에서 다음노드 == 이전노드를 체크해서 다시 위로 탐색하는걸 방지해줬다.
탐색을 하다가 더이상 내려갈 곳이 없을때 a[이전노드] += a[현재노드] 를 해주는 이유는
이 문제는 결국 모든 노드의 숫자를 더해서 0이 돼야 모든 숫자를 0으로 만들수있기 때문이다.
그래서 깊은곳까지 탐색을 마치고 올라갈 때 부모의 가중치에 현재 가중치를 더해주는거다.
result에는 현재 노드의 가중치를 더해 연산횟수를 기록해준다.

그렇게 끝까지 탐색을 마친다면 가중치 배열 a의 0번째에 모든 가중치를 더한 결과가 나온다.
이 결과가 0이라면 다 더해서 0이 나온거니 연산횟수 result를 출력해주면 된다.

하지만 이럼에도 불구하고 런타임 에러가 떴는데 여기서 시간을 많이 잡아먹었다.
그 이유는 !!!

마지막!!

내가 풀이한 언어가 자바스크립트 이기 때문이다.
더 정확히는 자바스크립트의 콜스택이 스택 오버플로우로 초과났기 때문이다.
계속 하다가 더이상 모르겠어서 다른언어를 사용해서 풀어보니 바로 풀린걸 보고 이런 결론을 내렸다.

그래서 재귀함수를 아래처럼 스택을 사용해 구현하는 방법으로 바꿔서 이 문제는 해결했따.
그러고 나니 틀렸다는 에러가 하나 남았는데 이는 더이상 스택 오버플로우때문에 발생하는게 아니었다.

프로그래머스에서 문제를 풀며 자료형보다 큰 값이 들어갔을때 저 에러가 많이 떴었는데
이번에도 그것때문에 발생하는 문제였다. 그래서 result를 BigInt로 바꾸고 마지막 문제도 해결했다.

정답코드

const solution = (a, edges) => {
  // 이전, 현재
  const stack = [[-1, 0]];
  const visited = Array.from({ length: a.length }, () => false);
  let graph = Array.from({ length: a.length }, () => []);
  let result = 0n;

  // 그래프 입력
  for (let i = 0; i < edges.length; i++) {
    const [a, b] = edges[i];
    graph[a].push(b);
    graph[b].push(a);
  }

  while (stack.length) {
    const [before, now] = stack.pop();

    // 마지막 아래쪽 노드에 도촉한 경우
    if (visited[now]) {
      a[before] += a[now];
      result += BigInt(Math.abs(a[now]));
      continue;
    }
    // 재귀함수처럼 한번더 부모노드에 들리기위해 넣어둠
    visited[now] = true;
    stack.push([before, now]);

    for (next of graph[now]) {
      if (visited[next]) continue;
      stack.push([now, next]);
    }
  }

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