[CodeKata] 프로그래머스: 11.6(토), 모두 0으로 만들기

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

단순하게, 간선이 많이 연결된 노드부터 주변값을 총합하는 방법으로 접근했다. 당연히, 예외상황이 있기 때문에 정답률이 낮게 나왔다.

function solution(a, edges) {
  const sum = a.reduce((a,b) => a+b)
  if (sum !== 0) return -1;
  
  const len = a.length;

  const besides = new Array(len).fill([]);
  edges.forEach(([a,b]) => {
    besides[a] = [...besides[a], b];
    besides[b] = [...besides[b], a];
  })
  
  let answer = 0;
  const idxs = Array.from({length: a.length}, (_,i) => i).sort((i1,i2) => besides[i2].length - besides[i1].length);

  while (a.find(e => e !== 0)) {
    const idx = idxs.shift();
    if (!idx) return -1;
    
    besides[idx].forEach(i => {
      const v = a[i];
      if (v === 0) return;
      a[idx] += v;
      a[i] = 0;
      answer += Math.abs(v);
    })
  }
  
  return answer;
}

 

🖇 리뷰

DFS를 활용한 풀이로, 재귀방식을 사용하면 콜스택 오버플로우가 발생하므로 stack을 활용한 것이다.

function solution(arr, edges) {
  if (arr.reduce((a, b) => a + b) !== 0) return -1

  const tree = new Array(arr.length).fill(0).map(() => new Array())
  const nums = arr.slice()
  let result = BigInt(0)

  edges.forEach(([a, b]) => {
    tree[a].push(b)
    tree[b].push(a)
  })

  const visited = new Array(arr.length).fill(false)
  const stack = [[0, null]]

  while (stack.length) {
    const [curr, parent] = stack.pop()

    if (visited[curr]) {
      result += BigInt(Math.abs(nums[curr]))
      nums[parent] += nums[curr]
      nums[curr] = 0
      continue
    }

    visited[curr] = true
    stack.push([curr, parent])

    for (const next of tree[curr]) {
      if (!visited[next]) stack.push([next, curr])
    }
  }
  return result
}

* 출처 : https://www.cckn.dev/problem-solve/(JS)%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EB%AA%A8%EB%91%90-0%EC%9C%BC%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0/

 

0. 총합 판정

• arr배열의 모든 합이 0이 아니면 만들수 있는 조건 자체가 성립되지 않는다. 이를 reduce() 로 계산한뒤, 아닐 경우 -1을 반환한다.

 

1. DFS 준비

• tree는 인접한 노드들을 담기 위한 이중배열이다. edges를 순회하며, a번째에는 b노드를, b번째는 a노드를 각각 담아주는 것이다.
• nums는 arr의 얕은복사를 한 배열, result는 반환할 결과값이다. Node.js의 Number.MAXSAFEINTEGER 한계값을 초과하기 때문에 BigInt() 자료형을 취해준다. (BigInt는 Number 원시값의 최대 안정치인 2^53-1 보다 큰 값을 표현하는 내장객체)
• visited는 노드 방문여부를 관리하는 체크배열, stack은 방문하는 노드정보를 담는 스택으로 [도착노드, 출발노드] 튜플 형태이다.

 

2. DFS 검사

• DFS는 while 반복문으로, stack 내 요소가 존재하는 동안 진행한다. 요소를 꺼내와서(pop), [curr, parent] 정보를 가져온다.
• curr 노드를 방문하지 않았다면(아래), visited를 true로 바꿔준다. 그리고, 현재노드([curr, parent])와 함께 인접노드(tree[curr]) 중 방문하지 않은 노드들을 모두 stack에 넣어준다.
• curr 노드를 방문했다면(다시 위), result에 nums[curr] 값을 더해준다. 그리고, 이 nums[curr] 값을 parent 노드로 옮겨준다.
• 여기서 continue를 하는 이유는, 다음 단계의 노드까지 우선적으로 방문하기 위해서이다. BFS는 너비탐색을 하기 때문에 근처노드부터 확인(shift)하지만, DFS는 깊이탐색을 하므로 맨 뒤의 값부터 가져온다.(pop)
• stack이 비면 모든 탐색이 완료된 것이다. 이 때, 최종적으로 누적된 result 값을 반환해주면 된다.

 

DFS가 재귀방식으로만 구현가능한 것으로 알고 있었으나, 이처럼 임의의 stack배열을 가지고 DFS를 만들 수 있음을 알았다.

 

BFS와의 차이점은, BFS는 주변부터 너비탐색을 하기 때문에 stack에서 shift()하여 먼저 누적된 요소부터 검사하고, visited를 우선 true로 관리한다.

이에 반해 DFS는 가장 깊은 노드부터 탐색해야 하므로 stack의 끝요소를 pop()하며, visited를 나중에 true로 치환해 우선 가장 깊은 레벨에 먼저 도달하게끔 한다.