Node.js) 백준 17471번: 게리맨더링

https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");


function main(input) {
  const N = +input.shift()
  const population = input.shift().split(' ').map(Number);
  const bridge = input.map(v => v.split(' ').filter((x, i) => i != 0).map(y => y - 1))
  let answer = Infinity;


  for (let i = 1; i < (1 << N) - 1; i++) {
    let visited = new Array(N).fill(null);
    let check = [false, false];

    for (let j = 0; j < N; j++) {
      if (check[1] && check[0]) break;
      if ((i & (1 << j)) && !check[1]) {
        check[1] = true;
        let q = [];
        q.push(j);
        visited[j] = 1;
        while (q.length > 0) {
          const now = q.shift();
          for (let k = 0; k < bridge[now].length; k++) {
            const next = bridge[now][k];
            if (i & (1 << next) && !visited[next]) {
              q.push(next)
              visited[next] = 1;
            }
          }
        }
      } else if (!(i & (1 << j)) && !check[0]) {
        check[0] = true;
        let q = [];
        q.push(j);
        visited[j] = 2;
        while (q.length > 0) {
          const now = q.shift();
          for (let k = 0; k < bridge[now].length; k++) {
            const next = bridge[now][k];
            if (!(i & (1 << next)) && !visited[next]) {
              q.push(next)
              visited[next] = 2;
            }
          }
        }
      }
    }

    if (visited.length == visited.filter(v => v != null).length) {
      let team1 = 0;
      let team2 = 0;
      visited.forEach((v, i) => {
        if (v == 1) {
          team1 += population[i]
        } else {
          team2 += population[i]
        }
      })
      const diff = Math.abs(team1 - team2);
      if (answer > diff) answer = diff
    }
  }
  if (answer == Infinity) {
    answer = -1;
  }
  console.log(answer)
}

main(input)