[알고리즘/백준/16918] 봄버맨(BFS, Nodejs)

문제

---

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

16918번: 봄버맨

 

풀이

---

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

const [r, c, n] = N.split(" ").map(Number);
const board = arr.map((row) => row.split(""));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
let time = 1;
let timeBoard = Array.from({ length: r }, () => Array(c).fill(0));

// 폭탄 설치 시간 추가
for (let i = 0; i < r; i++) {
  for (let j = 0; j < c; j++) {
    if (board[i][j] === "O") timeBoard[i][j] = 3; // 폭발할 시간 저장
  }
}

while (time <= n) {
  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      // 1) 빈 자리에 새로운 폭탄 설치
      if (time % 2 === 0 && board[i][j] === ".") {
        board[i][j] = "O";
        timeBoard[i][j] = time + 3; // 폭발할 시간 저장
      }

	// 2) // bfs 돌면서 3초 지난 경우 폭탄 폭발
      if (time % 2 === 1 && time === timeBoard[i][j]) {
        board[i][j] = ".";
        
        for (let k = 0; k < dx.length; k++) {
          const nx = i + dx[k];
          const ny = j + dy[k];

		// 4방향 가운데 폭탄이면서 현재 초(time)에 폭발하지 않는 경우
         if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
         
          if (board[nx][ny] === "O" && time !== timeBoard[nx][ny]) {
            // 자기자신 포함 4방향
            board[nx][ny] = ".";
            timeBoard[nx][ny] = 0;
          }
        }
      }
    }
  }
  time += 1;
}

console.log(board.map((row) => row.join("")).join("\n"));

짝수 시간(2, 4, 6,.. 초)에는 빈 자리에 폭탄을 채워주고, 홀수 시간(1, 3, 5,...초)에는 폭탄이 폭발한다. 

각 폭탄이 폭발하는 시간은 설치한 후 3초 이후이므로 이 시간을 timeBoard라는 배열을 만들어 저장한다. 

 

n초가 될 때까지 

1) 짝수 초이면서 빈 공간에는 폭탄을 채워주고, 폭발할 시간을 저장한다. 

2) 홀수 초이면서 폭발할 시간이 현재 시간인 경우 BFS로 현재 지점 기준으로 4방향을 탐색해 이동 가능한 지점이면 폭발한다.

이때, 유의해야 할 점은 4방향에 있는 지점 가운데 폭발해야 할 지점은 건너뛰어야한다는 것이다.(time !== timeBoard[nx][ny])

이는 해당 폭탄의 4방향에 있는 지점도 마찬가지로 폭발을 시켜야 하는데, 만약 현재 상황에서 해당 폭탄을 터뜨리면 다른 지점으로 탐색을 하지 않게 되기 때문이다. 

 

그리고 모든 작업을 완료하고 나면 시간을 증가시켜 준다. 

 

반대로 짝수 초일 때와 홀수 초일 경우를 나누어 격자판을 돌면서 필요한 작업을 수행할 수도 있다.

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

const [R, C, N] = n.split(" ").map(Number);
const board = arr.map((row) => row.split(""));
const timeBoard = Array.from({ length: R }, () => Array(C).fill(0));
const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
];

let time = 1;

// 초기에 설치되어 있는 폭탄이 폭발할 시간 지정
for (let i = 0; i < R; i++) {
  for (let j = 0; j < C; j++) {
    if (board[i][j] === "O") timeBoard[i][j] = 3;
  }
}


while (time <= N) {
  // 짝수 초
  if (time % 2 === 0) {
    for (let i = 0; i < R; i++) {
      for (let j = 0; j < C; j++) {
        if (board[i][j] === ".") {
          board[i][j] = "O";
          timeBoard[i][j] = time + 3;
        }
      }
    }
  } else {
  // 홀수 초
    for (let i = 0; i < R; i++) {
      for (let j = 0; j < C; j++) {
        if (board[i][j] === "O" && timeBoard[i][j] === time) {
          // 폭탄 폭발
          board[i][j] = ".";

          for (let k = 0; k < 4; k++) {
            const nx = i + dir[k][0];
            const ny = j + dir[k][1];
          

            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            // 4방향 가운데 폭탄이면서 현재 초(time)에 폭발하지 않는 경우
            if (board[nx][ny] === "O" && timeBoard[nx][ny] !== time)
              board[nx][ny] = ".";
          }
        }
      }
    }
  }

  time += 1;
}