[프로그래머스] 전력망을 둘로 나누기 (JS)

풀이 과정

1. 주어진 배열 값을 객체에 단방향 연결 리스트로 저장
2. 객체의 각 키에 대해 반복
3. 각 키의 값에 대해 반복
4. 현재 노드와 연결을 끊었다고 가정하고 현재 키에서 연결된 노드의 수, 현재 노드에서 연결된 노드 수의 차 구하기: DFS
   저장된 차보다 작으면 갱신
5. 모든 탐색이 완료되면 값 리턴

코드

function solution(n, wires) {
  let result = Infinity;
  const obj = {};
  wires.forEach(([k, v]) => {
    if (!obj[k]) obj[k] = [];
    if (!obj[v]) obj[v] = [];
    obj[k].push(v);
    obj[v].push(k);
  });

  const countNodes = (start, cut) => {
    const visited = Array(n + 1).fill(false);
    const q = [start];
    let count = 0;
    while (q.length) {
      const curr = q.pop();
      if (curr === cut || visited[curr]) continue;
      visited[curr] = true;
      ++count;
      for (const el of obj[curr]) q.push(el);
    }
    return count;
  };

  for (const k of Object.keys(obj)) {
    for (const v of obj[k]) {
      const gap = Math.abs(countNodes(k, v) - countNodes(v, Number(k)));
      if (gap < result) result = gap;
    }
  }

  return result;
}

🦾

Object의 key는 문자열이다...