치즈

• https://www.acmicpc.net/problem/2638

문제풀이

bfs나 dfs를 이용해서 푸는 문제이다.
처음에는 그냥 공기에 닿아있는 곳을 기준으로 했었는데, 문제를 자세히 읽어보니 '외부공기'만 이였다. 그래서, 가장자리는 항상 외부공기이므로, 가장자리 기준으로 dfs를 돌려서 외부공기를 체크해줬다.

그 후에는 외부공기를 계속 확인해주면서 치즈를 없애고 time을 계산했다.

소스코드

const log = console.log;
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

const [M, N] = input[0].split(" ").map(e => +e);
const space = Array.from(Array(M), () => Array(N).fill(0));
const cheeses = [];
let count = 0;
const dx = [1,-1,0,0];
const dy = [0,0,1,-1];
input.slice(1, M+1).map((e, y) => e.split(" ").map((el, x) => {
  el = Number(el);
  if(el === 1){
    count++;
    space[y][x] = 1
    cheeses.push([y, x]);
  }
}));

const markAir = () => {
  const queue = [[0,0]];
  const visited = Array.from(Array(M), () => Array(N).fill(false));
  while(queue.length){
    const [y, x] = queue.pop();
    for(let i=0 ; i<4 ; i++){
      const nx = x + dx[i];
      const ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= N || ny >= M || visited[ny][nx] || space[ny][nx] === 1) continue;
      visited[ny][nx] = true;
      space[ny][nx] = -1;
      queue.push([ny, nx]);
    }
  }
}

const meltingCheese = (y, x) => {
  let air = 0;
  for(let i=0 ; i<4 ; i++){
    const ny = y + dy[i];
    const nx = x + dx[i];
    if(ny < 0 || nx < 0 || ny >= M || nx >= N || space[ny][nx] === 1 || space[ny][nx] === 0) continue;
    air++;
  }
  return air >= 2 ? true : false;
}

let time = 0;

while(count){
  markAir();
  let meltedCheese = [];
  for(let i=0 ; i<cheeses.length ; i++){
    const [y, x] = cheeses[i];
    if(space[y][x] === -1) continue;
    if(meltingCheese(y, x)){
      meltedCheese.push([y, x]);
      count--;
      continue;
    }
  }
  meltedCheese.forEach(([y, x]) => space[y][x] = -1);
  time++;
}

log(time);