[백준] 2638 치즈 - javascript

📌 문제

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

📌 풀이

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

const [n, m] = input.shift().split(" ").map(Number);
const arr = input.map(i => i.split(" ").map(Number));
const visit = Array.from({ length: n + 1 }, () =>
  Array.from({ length: m + 1 }, () => 1)
);
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
let ans = 0;

const checkInOut = () => {
  const q = [];
  q.push([0, 0]);
  visit.map(v => v.fill(0));

  while (q.length) {
    const [x, y] = q.shift();
    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [x + dx[i], y + dy[i]];
      if (
        nx >= 0 &&
        nx < n &&
        ny >= 0 &&
        ny < m &&
        !visit[nx][ny] &&
        arr[nx][ny] !== 1
      ) {
        visit[nx][ny] = 1;
        arr[nx][ny] = 2;
        q.push([nx, ny]);
      }
    }
  }
};

while (1) {
  let isMelt = false;
  checkInOut();

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (arr[i][j] === 1) {
        let cnt = 0;
        for (let k = 0; k < 4; k++) {
          const nx = i + dx[k];
          const ny = j + dy[k];
          if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] === 2)
            cnt++;
        }
        if (cnt >= 2) {
          arr[i][j] = 3;
          isMelt = true;
        }
      }
    }
  }
  if (isMelt) {
    arr.forEach(row =>
      row.forEach(element => {
        if (element === 3) element = 2;
      })
    );
  }
  ans++;

  let arrHasCheese = false;

  arr.forEach(row =>
    row.forEach(element => {
      if (element === 1) arrHasCheese = true;
    })
  );

  if (!arrHasCheese) break;
}
console.log(ans);

✔ 알고리즘 : 구현 + BFS

✔ 좌표정보 👉 0: 내부공기, 1: 치즈, 2: 외부공기, 3: 녹은상태

✔ 치즈를 녹이기 전에 항상 외부공기와 내부공기를 나누는 작업이 필요하므로 (0,0) 부터 BFS 탐색을 통해 도달할 수 있는 모든 좌표를 검색하여 그 값을 2로 설정하였다.

✔ 이제 치즈를 녹이는 작업을 해야하므로 해당좌표가 치즈(1)인 경우 네 방향 탐색을 하여 외부공기가 2개 이상인 경우만 녹인다.

✔ 바로 녹이면 현재 시간에 영향을 주므로 3으로 설정하고 2중 for문으로 arr탐색을 마친 후 외부공기로 바꿔준다.

✔ 치즈가 있으면 계속 반복하고 치즈가 없으면 while문을 종료한다.

✔ 난이도 : 백준 기준 골드 4