[백준] 18045 경쟁적 전염 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, k] = input.shift().split(" ").map(Number);
const [s, x, y] = input.slice(-1)[0].split(" ").map(Number);
const arr = input.slice(0, -1).map(i => i.split(" ").map(Number));
const virusQueue = Array.from({ length: k + 1 }, () => []);
const visited = Array.from({ length: n }, () =>
  Array.from({ length: n }, () => false)
);
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (arr[i][j] === 0) continue;

    visited[i][j] = true;
    virusQueue[arr[i][j]].push([i, j]);
  }
}

for (let i = 0; i < s; i++) {
  for (let j = 1; j <= k; j++) {
    const nextVirusQueue = [];

    while (virusQueue[j].length) {
      const [cx, cy] = virusQueue[j].shift();

      for (let d = 0; d < 4; d++) {
        const [nx, ny] = [cx + dx[d], cy + dy[d]];

        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

        if (!visited[nx][ny] && arr[nx][ny] === 0) {
          visited[nx][ny] = true;
          arr[nx][ny] = j;
          nextVirusQueue.push([nx, ny]);
        }
      }
    }

    virusQueue[j] = nextVirusQueue;
  }
}

console.log(arr[x - 1][y - 1]);

✔️ 알고리즘 : 구현(BFS)

✔️ 바이러스 전파를 하는 문제로 bfs 문제이다. 하지만 우선순위가 번호가 낮은 바이러스부터 전파시켜야 하는 문제이다.

✔️ arr를 탐색하며 바이러스가 현재 존재하는 경우 바이러스 큐에 push한다. 바이러스 큐는 바이러스의 종류인 k개 만큼 만들어야 한다.

✔️ 1초에 전파할 수 있는 모든 바이러스를 전파시켜야 하므로 j for문을 통해 바이러스를 전파시켰다. 여기서 중요한 점은 기존의 bfs문제처럼 하나의 큐에서 모든 것을 처리하는 것이 아니라 시간에 따라 전파해야 하므로 1초동안 전파시킬 수 있는 모든 칸으로 전파한 후(nextVirusQueue에 push) 기존의 virusQueue를 nextVirusQueue로 바꿔줘야 한다.

virusQueue[j] = nextVirusQueue;

✔️ s초 동안 전파시킨 후 답을 출력한다.

✔️ 난이도 : 백준 기준 골드 5