백준 12886 돌 그룹

문제

제한 사항

입출력 예

풀이

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

const sol = (input) => {
  const numArr = input.map((e) => +e);
  const visited = Array.from(Array(1501), () => Array(1501).fill(0));
  const sum = numArr.reduce((a, c) => a + c, 0);
  if (sum % 3) {
    return 0;
  }

  const queue = [];
  visited[numArr[0]][numArr[1]] = 1;
  queue.push([numArr[0], numArr[1], numArr[2]]);

  while (queue.length) {
    let cur = queue.shift();
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (cur[i] < cur[j]) {
          const nx = cur[i] + cur[i];
          const ny = cur[j] - cur[i];

          if (visited[nx][ny]) continue;

          visited[nx][ny] = 1;
          queue.push([nx, ny, sum - nx - ny]);
        }
      }
    }
  }
  return visited[sum / 3][sum / 3] ? 1 : 0;
};

console.log(sol(input));

시간 초과를 해결하지 못했다. 확실한 건 아니지만 js의 고질적인 문제인 것 같다.

돌이 3개라 visited 배열을 3차원 배열로 만들 필요는 없다. 두 돌의 개수가 정해지만 나머지의 개수는 자동으로 정해지기 때문이다.

bfs를 끝내고 난 뒤 visited의 sum/3 , sum/3 을 확인해 방문한 기록이 있으면 세 수가 같아 질 수 있는 것이다.