[Node.js] 17142_연구소3

문제

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

 

 

풀이

본 문제는 이전에 풀이했던 연구소 문제의 다른 버전이며, 주어지는 수 만큼 바이러스를 활성화 했을 때 모든 공간에 바이러스가 확산되는 시간의 최소값을 구하는 문제다.

 

해당 문제에서는 조심해야할 포인트가 있다.

1. 바이러스가 확산될 때 비활성 바이러스는 넘어갈 수 있다.
2. (개인적으로 햇갈렸던 부분) 활성화할 바이러스의 조합을 정하는 로직

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e.split(' ').map(Number));

const [n, m] = input.shift();
const map = input.slice();
const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const virus = [];
const blank = [];
const active = new Array(m);
let answer = Infinity;

for (let i = 0; i < map.length; i++){
  for (let j = 0; j < map[0].length; j++){
    if (map[i][j] === 2) virus.push([i, j, 0])
    else if (map[i][j] === 0) blank.push([i, j]);
  }
}

const spread = (activePos) => {
  const temp = Array.from({length: n}, () => Array(n).fill(false));
  const que = [...activePos];
  let zeroCnt = blank.length;
  que.forEach(([y, x]) => {
    temp[y][x] = true;
  })
  while (que.length > 0) {
    const [y, x, tCnt] = que.shift();
    for (let i = 0; i < 4; i++){
      const nY = y + dir[i][0];
      const nX = x + dir[i][1];
      if (nY < 0 || nY >= n || nX < 0 || nX >= n) continue;
      else if (temp[nY][nX] || map[nY][nX] === 1) continue;
      
      if (map[nY][nX] === 0) zeroCnt--;
      if (zeroCnt === 0) {
        answer = Math.min(answer, tCnt + 1);
        return;
      }
      
      temp[nY][nX] = true;
      que.push([nY, nX, tCnt + 1]);
    }
  }
}

const dfs = (start, depth) => {
  if (depth === m) {
    spread(active);
    return;
  }
  for (let i = start; i < virus.length; i++){
    active[depth] = virus[i];
    dfs(i + 1, depth + 1);
  }
}

if (blank.length === 0) console.log(0)
else {
  dfs(0, 0);
  console.log(answer === Infinity ? -1 : answer)
}