백준 14500 < 테트로미노 > JavaScript

📍문제 링크

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

14500번: 테트로미노

 

📍알고리즘 분류

- 구현

- 브루트포스

 

📍문제 풀이

1. 기존 폴리오미노의 회전과 대칭을 고려했을 때, 총 몇 개의 형태가 필요할까?

 

총 19개의 형태가 필요하다.

 

2. 보드에서 곡선형 폴리오미노의 점수를 쉽게 계산하는 방법은?

 

직사각형을 만들고 빈 칸은 0으로 채운 뒤 보드의 각 숫자와 곱하여 합을 구하면 된다.

 

📍의사 코드

1. 가능한 폴리오미노의 형태를 배열에 저장한다

2. 형태별 (총 19개) 계산을 시행하여 최종 답을 출력하는 반복문을 생성한다

3. 주어진 좌표평면에서 형태를 크기에 맞게 넣어보며 최댓값을 구하는 반복문을 생성한다

4. 형태와 좌표평면에서의 위치가 주어졌을 때, 넓이를 계산하는 반복문을 생성한다

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [n, m] = in1.split(" ").map(Number);
const board = in2.map((row) => row.split(" ").map(Number));
const polyomino = [
  // box
  [
    [1, 1],
    [1, 1],
  ],
  // bar
  [[1, 1, 1, 1]],
  [[1], [1], [1], [1]],
  // T
  [
    [1, 1, 1],
    [0, 1, 0],
  ],
  [
    [0, 1, 0],
    [1, 1, 1],
  ],
  [
    [1, 0],
    [1, 1],
    [1, 0],
  ],
  [
    [0, 1],
    [1, 1],
    [0, 1],
  ],
  // thunder
  [
    [1, 1, 0],
    [0, 1, 1],
  ],
  [
    [0, 1, 1],
    [1, 1, 0],
  ],
  [
    [1, 0],
    [1, 1],
    [0, 1],
  ],
  [
    [0, 1],
    [1, 1],
    [1, 0],
  ],
  // L
  [
    [1, 0],
    [1, 0],
    [1, 1],
  ],
  [
    [1, 1, 1],
    [1, 0, 0],
  ],
  [
    [1, 1],
    [0, 1],
    [0, 1],
  ],
  [
    [0, 0, 1],
    [1, 1, 1],
  ],
  [
    [1, 0, 0],
    [1, 1, 1],
  ],
  [
    [1, 1],
    [1, 0],
    [1, 0],
  ],
  [
    [0, 1],
    [0, 1],
    [1, 1],
  ],
  [
    [1, 1, 1],
    [0, 0, 1],
  ],
];

const calcArea = (shape, w, h, rowNum, colNum) => {
  let area = 0;
  for (let i = 0; i < w; i++) {
    for (let j = 0; j < h; j++) {
      area += board[i + rowNum][j + colNum] * shape[i][j];
    }
  }
  return area;
};

const getMax = (shape, width, height) => {
  let max = 0;
  for (let i = 0; i < n - width + 1; i++) {
    for (let j = 0; j < m - height + 1; j++) {
      max = Math.max(max, calcArea(shape, width, height, i, j));
    }
  }
  return max;
};

const solution = () => {
  let answer = 0;
  for (let shape of polyomino) {
    const [wSize, hSize] = [shape.length, shape[0].length];
    answer = Math.max(answer, getMax(shape, wSize, hSize));
  }
  return answer;
};

console.log(solution());

 

📍리뷰

- 형태의 가로,  세로 길이를 반복문에서 매번 계산하지 않고, 미리 계산하여 매개변수로 넘겨주니 시간을 줄일 수 있었다