[백준 5427번] BFS(너비 우선 탐색) - 불

✨ 문제 ✨

✨ 정답 ✨

// 시간초과
const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();


// const fs = require('fs'); 
// let input = fs.readFileSync("/dev/stdin").toString().trim();

input = input.split('\n')

const N = +input.shift();
let dx = [-1, 0, 1, 0]
let dy = [0, -1, 0, 1]


const solution = (w, h, building, start) => {
  let queue = [];
  // let count = 0;
  let isPossible = false;
  // 상근이 중복막기
  let visited = Array.from({ length: h }, () => new Array(w).fill(false))
  // 불 먼저 넣기
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (building[i][j] === '*') {
        queue.push([i, j, 0])
      }
    }
  }
  // 상근이 처음 위치 넣기
  queue.push([...start, 0])
  while (queue.length) {
    let [currentX, currentY, count] = queue.shift();
    let willBeFire = []
    // 불이라면
       if (building[currentX][currentY] === '*') {
      for (let i = 0; i < dx.length; i++) {
        let nextX = currentX + dx[i];
        let nextY = currentY + dy[i];
        if (nextX < h && nextY < w&&nextX>=0&&nextY>=0) {
          if (building[nextX][nextY] === '#') {
            continue;
          } else if (building[nextX][nextY] === '.') {
            willBeFire.push([nextX, nextY, count])
          }
        }
      }
      for (let i = 0; i < willBeFire.length; i++) {
        let [x, y, count] = willBeFire[i]
        // 불 옮겨주기
        building[x][y] = '*'
      }
    }
    // 불이 아니라면
    else if (building[currentX][currentY] === '.' || building[currentX][currentY] === '@') {
      if (currentX===0||currentY===0||currentX===h||currentY===w){
        return 1;
      }
      
      visited[currentX][currentY] = true;
      count += 1;
      for (let i = 0; i < dx.length; i++) {
        let nextX = currentX + dx[i];
        let nextY = currentY + dy[i];   
        if (nextX < h && nextY < w&&nextX>=0&&nextY>=0&&building[nextX][nextY]==='.') {
          if (visited[nextX][nextY] === true) {
            continue;
          } else {
            if (building[nextX][nextY] ===".") {
              queue.push([nextX, nextY, count]);
              visited[nextX][nextY]=true;
              for (let m=0;m<h;m++){
                for (let n=0;n<w;n++){
                  if (building[m][n]==='*'){
                    queue.push([m, n, count])
                  }
                }
              }
            }
            if ((nextX === h-1 || nextY === w-1 || nextX === 0 || nextY === 0)&&building[nextX][nextY]==='.') {
              isPossible = true;
              count += 1;
              return count;
            }
          }
        }
      }
    }
  }


  if (isPossible === false) {
    return 'IMPOSSIBLE';
  } else {
    return count
  }
}

for (let i = 0; i < N; i++) {
  let [w, h] = input.shift().split(' ').map((el) => +el);
  let building = input.splice(0, h).map((el) => el.trim().split(''))
  let start = [];
  for (let j = 0; j < h; j++) {
    for (let t = 0; t < w; t++) {
      if (building[j][t] === '@') {
        start.push(j, t)
      }
    }
  }
 if (start.length>0){
  console.log(solution(w, h, building, start))
 }else{
  console.log("IMPOSSIBLE")
 }

}

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡

BFS 문제 풀 때마다 x, y 순서를 헷갈려한다.
시간초과...를 항상 염두에 두고 풀어야 하는데 어떻게 하는건지 모르겠다.