🎲 백준 11967번 불켜기

백준 11967번

🎨 참고
💊 다음 방을 갈때 불이 안켜져있는 경우 candidates에 추가하고 불을 키는 과정에서 candidates에 있으면 queue에 넣어주는 것이 핵심이다.

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input.shift().split(" ").map(Number);
const switchArr = Array.from(new Array(N + 1), () =>
  Array.from(new Array(N + 1), () => [])
);

//0:불꺼짐 1:불켜짐 2:방문함
const lightArr = Array.from(new Array(N + 1), () => new Array(N + 1).fill(0));

const candidates = new Set();

for (let i = 0; i < M; i++) {
  const [x, y, a, b] = input[i].split(" ").map(Number);
  switchArr[y][x].push([a, b]);
}

const dir = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];

let answer = 1;
const queue = [[1, 1]];
lightArr[1][1] = 2;
const bfs = () => {
  while (queue.length) {
    const [x, y] = queue.shift();

    answer;
    for (let i = 0; i < switchArr[y][x].length; i++) {
      const [onX, onY] = switchArr[y][x][i];
      if (lightArr[onY][onX] === 0) {
        lightArr[onY][onX] = 1;
        answer++;
        if (candidates.has(JSON.stringify([onX, onY]))) {
          queue.push([onX, onY]);
        }
      }
    }
    for (let d = 0; d < 4; d++) {
      const [nextX, nextY] = [x + dir[d][0], y + dir[d][1]];
      if (
        nextX < 1 ||
        nextY < 1 ||
        nextX > N ||
        nextY > N ||
        lightArr[nextY][nextX] === 2
      )
        continue;

      if (lightArr[nextY][nextX] === 0) {
        candidates.add(JSON.stringify([nextX, nextY]));
      } else {
        lightArr[nextY][nextX] = 2;
        queue.push([nextX, nextY]);
      }
    }
  }
};

bfs();
console.log(answer);