[JS][백준]2636_치즈

문제 번호

2636번: 치즈

 

 

 

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

 

문제 풀이

 BFS를 사용하면 간단하게 풀 수 있는 문제이다. 

 문제에서 가장자리의 'X'에는 치즈를 놓지 않는다고 했다. 그러므로 (0,0)은 항상 'X' 이며, 항상 치즈가 없다. 때문에 BFS를 (0,0)에서 시작하여 '상,하,좌,우'로 탐색하면서 다음칸이 '공기'일때와 '치즈'일때를 나누어서 구현하면 된다. 다음칸이 '공기'일때는 Queue에 넣어주고 보통의 BFS처럼 진행하고 '치즈'일때는 Queue에 넣지 않는다. 이때 치즈가 녹는다고 BFS를 진행하면서 '1'에서 '0'으로 바로 바꾸어주면 문제가 발생한다. 그러므로 다음칸이 치즈 일때는 '1'에서 '2'로 바꿔준다음 BFS가 모두 끝난후에 한번에 '2'로 표시된 치즈를 '0'으로 녹여주었다.

 

문제에서 치즈가 모두 녹을때까지 진행하라고 하였으니 치즈가 모두 사라질때까지 BFS를 진행하면 된다.

 

전체코드

const input = require('fs').readFileSync('치즈/input.txt').toString().split('\n');
const [row, col] = input[0].split(' ').map(Number);
let cheez = new Array(row).fill(null).map(_ => new Array(col).fill(0));
let total = 0;  // 처음 치즈의 칸수.
let answerTime = 0; // 모두 녹는데 걸린 시간.

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

function BFS(){
  let past = total;  
  let visited = new Array(row).fill(null).map(_ => new Array(col).fill(false));
  let q = [];
  q.push([0,0]);

  while(q.length !== 0){
    let curr = q.shift();
    let curY = curr[0];
    let curX = curr[1];

    for(let next=0; next<4; next++){
      let nextY = curY + dy[next];
      let nextX = curX + dx[next];

      if( nextY <0 || nextY >= row || nextX < 0 || nextX >= col )
        continue;

      // 다음칸이 '공기'인 경우.
      if (!visited[nextY][nextX] && cheez[nextY][nextX] === 0){
        visited[nextY][nextX] = true;
        q.push([nextY, nextX]);        
      }
      // 다음칸이 '치즈'인 경우
      else if(!visited[nextY][nextX] && cheez[nextY][nextX] === 1){
        visited[nextY][nextX] = true;
        total--;
        cheez[nextY][nextX] = 2;  // 삭제 대기.
      }
    }
  }  
  answerTime++;

  if(total === 0){
    console.log(answerTime);
    console.log(past);
    return false;
  }   

  // 공기와 닿은 치즈를 녹인다.
  for(let i=0; i<cheez.length; i++){  
    for(let j=0; j<cheez[i].length; j++){
      if (cheez[i][j] === 2)
        cheez[i][j] = 0;
    }
  }
  return true;
}

function sol(){
  while(BFS());
}

function insert(){
  for (let i=0; i<row; i++){    
    let temp = input[i+1].split(' ').map(Number);
    for (let j=0; j<col; j++){
      cheez[i][j] = temp[j];
      if(cheez[i][j] === 1)
        total++;
    }
  }
  sol()
}

insert();

특이사항