[백준][구현] 21610 마법사 상어와 피바라기 NodeJs 구현

목차

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

문제

 

문제 구현 방향

문제의 흐름만 잘따라가면 풀 수 있다. 주의할 부분은 순환 좌표와 방문했던 구름의 처리이다.

 

 

순환 좌표

주의해야 할 점은 순환좌표를 다루기 때문에 인덱스를 0부터 시작해야 한다.

 let sx = dir[d][0] * s;
  let sy = dir[d][1] * s;

  for (let i = 0; i < cloud.length; i++) {
    let nx = (((cloud[i][0] + sx) % N) + N) % N;
    let ny = (((cloud[i][1] + sy) % N) + N) % N;
    cloud[i] = [nx, ny];
  }

 

구름의 방문 처리

아래와 같이 방문을 했는지 검사하면 시간초과가 발생한다..

따라서 visit배열을 만들어 주어 검사해야 한다.

function incheck(x, y, prev) {
  for (let i = 0; i < prev.length; i++) {
    let [a, b] = prev[i];
    if (a === x && b === y) {
      return 1;
    }
  }
  return 0;
}

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [N, M] = input[0].trim().split(" ").map(Number);
let info = [];
let board = Array.from(Array(N + 1), () => Array(N + 1));

let dir = [
  [-1, 0],
  [-1, -1],
  [0, -1],
  [1, -1],
  [1, 0],
  [1, 1],
  [0, 1],
  [-1, 1],
];

let crossdir = [
  [1, 1],
  [1, -1],
  [-1, 1],
  [-1, -1],
];
for (let i = 1; i <= N; i++) {
  let ar = input[i].trim().split(" ").map(Number);
  for (let j = 0; j < ar.length; j++) {
    board[i - 1][j] = ar[j];
  }
}
for (let i = N + 1; i < input.length; i++) {
  let [a, b] = input[i].trim().split(" ").map(Number);
  info.push([a - 1, b]);
}
let cloud = [];
//x, y
cloud.push([0, N - 1], [1, N - 1], [0, N - 2], [1, N - 2]);

function moving(cloud, d, s, visited) {
  let sx = dir[d][0] * s;
  let sy = dir[d][1] * s;

  for (let i = 0; i < cloud.length; i++) {
    let nx = (((cloud[i][0] + sx) % N) + N) % N;
    let ny = (((cloud[i][1] + sy) % N) + N) % N;
    cloud[i] = [nx, ny];
  }

  for (let i = 0; i < cloud.length; i++) {
    board[cloud[i][1]][cloud[i][0]]++;
    visited[cloud[i][1]][cloud[i][0]] = 1;
  }
}

function duplicating(prev) {
  for (let i = 0; i < prev.length; i++) {
    let cnt = 0;
    for (let j = 0; j < 4; j++) {
      let nx = prev[i][0] + crossdir[j][0];
      let ny = prev[i][1] + crossdir[j][1];
      if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
      if (board[ny][nx]) cnt++;
    }
    board[prev[i][1]][prev[i][0]] += cnt;
  }
}

function makeCloud(cloud, visited) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (board[i][j] >= 2 && !visited[i][j]) {
        cloud.push([j, i]);
        board[i][j] = Math.max(0, board[i][j] - 2);
      }
    }
  }
}

function counting() {
  let sum = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      sum += board[i][j];
    }
  }
  console.log(sum);
}
for (let i = 0; i < info.length; i++) {
  let [d, s] = info[i];
  let visited = Array.from(Array(N + 1), () => Array(N + 1).fill(0));
  moving(cloud, d, s, visited);
  let prev = [...cloud];
  cloud = [];
  duplicating(prev);
  makeCloud(cloud, visited);
}
counting();