백준 16918 봄버맨

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

문제

일반적인 구현 문제로 볼 수 있겠지만, 깡구현으로 풀다보면 결국 시간초과로 풀지 못하는 문제이다. 해당 문제는 시뮬레이션 결과를 보고 해당 결과에서 나타나는 패턴을 이용하여 해결하는 문제이다.

힌트를 보면 보다 잘 이해할 수 있다. 초기 상태 이후, 2초 4초, 6초 등 각 짝수 초마다는 비어 있는 칸에 모두 폭탄을 설치하는 초이기 때문에 모두 O로 가득 차 있다. 하지만 3초의 경우와 5초의 경우가 다른데, 3초는 기존 초기 상태에서 모든 폭탄이 설치된 뒤, 맨 처음 폭탄이 있던 자리들이 터지는 경우이다. 반면 5초는 기존 초기 상태와 동일한 값이 나온다는 패턴을 알 수 있다.

따라서 짝수 초일 때 → 모든 칸이 폭탄으로 1초, 이후 4초 간격으로 → 초기 상태 3초부터 4초 간격으로 → 초기 상태에서 설치한 폭탄들이 터졌을 때 의 경우로 나눠서 이 때마다 알맞은 패턴에 대한 값을 찍으면 된다.

4초 간격으로 나오는 이유는 폭탄은 최초 폭탄이 아닌 이상, 이후 설치하는 폭탄은 3초 뒤에 터지기 때문에 설치 -> 폭탄(있으면 터짐) -> 설치 -> 처음에 설치했던게 터짐의 순서대로 간다고 생각하면 이해가 가능하다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [r, c, n] = inputs[0].split(" ").map(Number);
 
const map = inputs.slice(1).map((r) => Array.from(r));
if (n % 2 === 0) {
  console.log("O".repeat(c).concat("\n").repeat(r).trim());
  process.exit(0);
}
 
if (n === 1) {
  console.log(grid.map((row) => row.join("")).join("\n"));
  process.exit(0);
}
 
const dLoc = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];
 
let firstBoom = Array.from({ length: r }, () => new Array(c).fill("O"));
for (let i = 0; i < r; i++) {
  for (let j = 0; j < c; j++) {
    if (map[i][j] === "O") {
      firstBoom[i][j] = ".";
      for (const [dx, dy] of dLoc) {
        const nRow = i + dx;
        const nCol = j + dy;
        if (nRow >= 0 && nRow < r && nCol >= 0 && nCol < c) {
          firstBoom[nRow][nCol] = ".";
        }
      }
    }
  }
}
 
let secondBoom = Array.from({ length: r }, () => new Array(c).fill("O"));
for (let i = 0; i < r; i++) {
  for (let j = 0; j < c; j++) {
    if (firstBoom[i][j] === "O") {
      secondBoom[i][j] = ".";
      for (const [dx, dy] of dLoc) {
        const nRow = i + dx;
        const nCol = j + dy;
        if (nRow >= 0 && nRow < r && nCol >= 0 && nCol < c) {
          secondBoom[nRow][nCol] = ".";
        }
      }
    }
  }
}
let result;
//처음 터졌을 때
if (n % 4 === 3) {
  result = firstBoom;
  // 원래 상태 Or 두번째 폭발
} else if (n % 4 === 1) {
  if (n === 1) result = map;
  //1초 후면서 3초 후일 때
  else result = secondBoom;
}
 
console.log(result.map((row) => row.join("")).join("\n"));