[백준 11967] 불켜기 with node.js

📌 문제

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

📌 풀이

• 정말 어려웠다..ㅠ
• buttonHasRooms[i][j]에 (i,j)위치에 있을 때 불을 켤 수 있는 좌표들을 모두 추가해서 설정해 놓는다.
• 방문표시를 하는 visited, 방에 불을 켰는지 확인하는 lightOnInRoom 을 만들어서 각각의 상태에 대해서 표시해준다.
• 1) 현재 위치(currX,currY)에서 불을 켤 수 있는 곳들을 모두 방문하면서 불이 꺼져있다면 불을 키고 lightOnInRoom에 표시하고 roomsLightOn를 1씩 증가시킨다.
  -> 이 때, 새로 불을 켠 방의 상하좌우를 탐색하면서 방문한 적이 있다면 queue에 추가한다.
  -> 새로 불을 켰기 때문에 다시 방을 검사해야하고 그렇기 때문에 큐에 추가하는 것이다.
• 2) 현재 위치(currX,currY)에서 상하좌우를 확인하며 방문한 적이 없는데 이미 불이 켜져있다면 다시 검사해야하기 때문에 queue에 추가한다.

📌 코드

const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString().trim()
    : `4 6
1 1 2 2
2 2 3 3
3 3 4 4
2 2 1 2
3 3 3 2
4 4 4 3`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const getMaxRoomsLightOn = () => {
  const visited = Array.from(new Array(N + 1), () => new Array(N + 1).fill(false));
  const lightOnInRoom = Array.from(new Array(N + 1), () => new Array(N + 1).fill(LIGHT_OFF));
  let roomsLightOn = 1;

  visited[1][1] = true;
  lightOnInRoom[1][1] = LIGHT_ON;

  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  const queue = [[1, 1]];

  while (queue.length) {
    const [currX, currY] = queue.shift();
    for (let [roomX, roomY] of buttonHasRooms[currX][currY]) {
      if (!lightOnInRoom[roomX][roomY]) {
        lightOnInRoom[roomX][roomY] = LIGHT_ON;
        roomsLightOn += 1;

        for (let i = 0; i < 4; i++) {
          let nextRoomX = roomX + dx[i];
          let nextRoomY = roomY + dy[i];

          if (nextRoomX < 1 || nextRoomY < 1 || nextRoomX > N || nextRoomY > N) continue;
          if (visited[nextRoomX][nextRoomY]) {
            queue.push([nextRoomX, nextRoomY]);
          }
        }
      }
    }

    for (let i = 0; i < 4; i++) {
      let nextCurrRoomX = currX + dx[i];
      let nextCurrRoomY = currY + dy[i];

      if (nextCurrRoomX < 1 || nextCurrRoomY < 1 || nextCurrRoomX > N || nextCurrRoomY > N) {
        continue;
      }
      if (!visited[nextCurrRoomX][nextCurrRoomY] && lightOnInRoom[nextCurrRoomX][nextCurrRoomY]) {
        queue.push([nextCurrRoomX, nextCurrRoomY]);
        visited[nextCurrRoomX][nextCurrRoomY] = true;
      }
    }
  }

  return roomsLightOn;
};

const [LIGHT_OFF, LIGHT_ON] = [false, true];
const [N, M] = input().split(' ').map(Number);
const buttonHasRooms = Array.from(new Array(N + 1), () => new Array(N + 1));

for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= N; j++) {
    buttonHasRooms[i][j] = [];
  }
}

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

console.log(getMaxRoomsLightOn());