[백준][구현] 20058 마법사 상어와 파이어스톰 NodeJs 구현

목차

문제

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

 

문제 구현 방향

크게 방향 회전, 녹이기, bfs만 구해주면 되는 문제였다

회전하는 부분에서 많이 헤멨다..

 

 

 

구현 시 회전 부분

시계는 오른쪽 반시계는 왼쪽이라고 외우자

기준 좌표가 있을 때도 다를 것 없다 기준좌표만 더해주면 된다.

//시계 방향 회전
new_board[x][size - 1 - y] = board[y][x];

//반시계 방향 회전
new_board[size - x - 1][y] = board[y][x];

//특정 좌표(왼쪽 상단 기준 시계방향 회전)
new_board[i + l][j + size - 1 - y] = board[i + y][j + x];

//특정 좌표(왼쪽 상단 기준 반시계방향 회전)
new_board[i + size - 1 - x][j + y] = board[i + y][j + x];

 

 

 

 

 

코드 구현

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

let [N, M] = input[0].trim().split(" ").map(Number);
let meter = Math.pow(2, N);
input.splice(0, 1);
let Ls = input[input.length - 1].trim().split(" ").map(Number);
let board = Array.from(Array(meter), () => Array(meter));
let visit = Array.from(Array(meter), () => Array(meter).fill(0));

for (let i = 0; i < meter; i++) {
  let arr = input[i].trim().split(" ").map(Number);
  for (let j = 0; j < meter; j++) {
    board[i][j] = arr[j];
  }
}

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

function iceMelting() {
  let board2 = board.map((row) => [...row]);
  for (let i = 0; i < meter; i++) {
    for (let j = 0; j < meter; j++) {
      let flag = 0;
      for (let p = 0; p < 4; p++) {
        let nx = j + dx[p];
        let ny = i + dy[p];
        if (nx < 0 || nx > meter - 1 || ny < 0 || ny > meter - 1) continue;
        if (board[ny][nx] > 0) flag++;
      }
      if (flag < 3) {
        board2[i][j] -= 1;
        if (board2[i][j] <= 0) {
          board2[i][j] = 0;
        }
      }
    }
  }
  return board2;
}

function rotateAll(L) {
  let k = Math.pow(2, L);
  let board2 = board.map((row) => [...row]);
  for (let i = 0; i < meter; i += k) {
    for (let j = 0; j < meter; j += k) {
      let size = k;
      for (let p = 0; p < size; p++) {
        for (let l = 0; l < size; l++) {
          board2[i + l][j + size - 1 - p] = board[i + p][j + l];
        }
      }
    }
  }
  return board2;
}
//board2[i + p][j + l] = board[i + size - 1 - l][j + p];
let ans = 0;
function counting() {
  for (let i = 0; i < meter; i++) {
    for (let j = 0; j < meter; j++) {
      ans += board[i][j];
    }
  }
}
let biggest = 0;

function bfs(sx, sy) {
  let sum = 1;
  let queue = [];
  visit[sy][sx] = true;
  queue.push({ x: sx, y: sy });
  while (queue.length) {
    let { x, y } = queue.shift();

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx > meter - 1 || ny < 0 || ny > meter - 1) continue;

      if (visit[ny][nx] || board[ny][nx] <= 0) continue;
      queue.push({ x: nx, y: ny });
      visit[ny][nx] = true;
      sum += 1;
    }
  }
  biggest = Math.max(biggest, sum);
}
function print() {
  for (let i = 0; i < meter; i++) {
    for (let j = 0; j < meter; j++) {
      process.stdout.write(`${String(board[i][j])}`);
    }
    console.log();
  }
}

for (let i = 0; i < Ls.length; i++) {
  board = rotateAll(Ls[i]).map((row) => [...row]);

  board = iceMelting().map((row) => [...row]);
}
counting();
console.log(ans);

for (let i = 0; i < meter; i++) {
  for (let j = 0; j < meter; j++) {
    if (!visit[i][j] && board[i][j] > 0) {
      bfs(j, i);
    }
  }
}
console.log(biggest);