[baekjoon] 2636 치즈 (Javascript)

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

2636번: 치즈

---

알고리즘 : bfs

 

처음에 아무생각없이 풀다가 치즈 안에 있는 공기를 고려하지 못했다.

곰곰히 생각해보다가 항상 1을 기준으로만 bfs를 돌렸는데 이번 문제는 0을 기준으로 즉, 공기를 기준으로 bfs를 돌려보니 간단하게 풀렸다.

생각의 전환이 필요한 문제라고 생각한다.

 

let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());

let [n,m] = input.shift().split(" ").map(v=>+v);

let graph = input.map(v=>v.split(" ").map(val=>+val));


let dx = [0,1,0,-1];
let dy = [1,0,-1,0];

const bfs=(x,y,vis)=>{
  let queue = [];
  vis[x][y]=1;
  let count = 0;
  queue.push([x,y]);
  while(queue.length){
    let [cx,cy] = queue.shift();
    for(let dir=0;dir<4;dir++){
      let nx = cx+dx[dir];
      let ny = cy+dy[dir];

      if(nx<0||nx>=n||ny<0||ny>=m) continue;
      if(graph[nx][ny]===1&&vis[nx][ny]===0) {
        graph[nx][ny]=0;
        vis[nx][ny]=1;
        count++;
        continue;
      }
      if(vis[nx][ny]===1) continue;
      vis[nx][ny]=1;
      queue.push([nx,ny]);
    }
  }

  return count;
}

function solution() {
  // 한시간마다 겉부분이 사라짐 => 개수를 기록

  let cnt = [];


while(cnt.at(-1)!==0){

  let vis = new Array(n).fill().map(v=>new Array(m).fill(0));
  
  let count = bfs(0,0,vis);


  cnt.push(count);

}

  console.log(cnt.length-1);
  console.log(cnt.at(-2));


}

solution();