[알고리즘] 백준 2636 치즈 (JS)

간만에 답안보고 집적 풀린 문제다 !!

요구사항

1. 바깥을 기준으로 0(산소)와 붙어있는 1(치즈)을 순차적으로 제거
2. 그 과정에서 몇번이 걸리는지, 마지막에 사라지는 치즈의 개수

내풀이

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().split("\n");
const [col, row] = input[0].split(" ").map(Number);
let cheez = Array.from(new Array(col), () => new Array(row).fill(0));
for (let i = 0; i < col; i++) {
  let temp = input[i + 1].split(" ").map(Number);
  for (let j = 0; j < row; j++) {
    cheez[i][j] = temp[j];
  }
}
solution(col, row, cheez);
function solution(col, row, nums) {
  let time = 0;
  let ret = 100000;
  let cnt = 0;
  let dy = [-1, 0, 1, 0];
  let dx = [0, 1, 0, -1];
  let visited = Array.from(new Array(col), () => new Array(row).fill(0));
  const dfs = (y, x) => {
    for (let i = 0; i < 4; i++) {
      let ny = y + dy[i];
      let nx = x + dx[i];
      if (ny < 0 || nx < 0 || ny >= col || nx >= row || visited[ny][nx])
        continue;
      if (nums[ny][nx] == 1) {
        visited[ny][nx] = 2;
        continue;
      }
      visited[ny][nx] = 1;
      dfs(ny, nx);
    }
  };
  while (true) {
    dfs(0, 0);
    cnt = 0;
    for (let i = 0; i < col; i++) {
      for (let j = 0; j < row; j++) {
        if (visited[i][j] == 2) {
          nums[i][j] = 0;
          cnt++;
        }
        visited[i][j] = 0;
      }
    }
    if (!cnt) break;
    time++;
    ret = Math.min(ret, cnt);
  }
  console.log(time);
  console.log(ret);
}

드디어 백준이랑 연결해서 했다 ㅋㅋ 매번 입력값을 내가 처리해야해서 그냥
밑에 직접 작성하였는데 이번에는 입력으로 받아서 처리했고
풀이는 dfs()로 하였다 0(산소)를 기준으로 상하좌우 4방향을 처리하면서 1(치즈)를 인경우는 visited(방문리스트)에 산소와 같이 방문처리만하고 dfs는 하지않는다. 그렇게하면 0을 기준으로만 dfs가 돌고 붙어있는 1같은 경우는 방문처리만 된다.
그렇게 cheez배열에 치즈가 사라질때까지 0을 기준으로 dfs를 돌면서 없어지면 종료된다.