[백준] 테트로미노 | 자바스크립트 JS | 브루트포스, 구현 | G4

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

 

풀이 과정

격자판에 놓일 수 있는 모든 테트로미노의 형태를 그려보니 무려 19가지나 되었다. 델타 탐색하면서 19가지의 모양을 놓아보기엔 시간이 많이 걸릴 것 같았지만 그리던 와중 테트로미노들은 4개의 1x1 칸으로 조합되어있기 때문에 뼈대가 될 3개의 1x1칸으로 유형을 나누면 되겠다는 생각이 들었다.

 

뼈대(?)유형을 찾으면 나머지 하나 블럭만 붙였다 뗐다 하면서 검사할 수 있다. 꺽쇠 모양의 기준 블럭으로 나누니 오른쪽과 같이 6가지 조합이나 되어 왼쪽의 3가지 조합(가로 셋, 세로 셋, 정사각형)을 기준으로 진행했다.

 

기준점을 (0, 0)이라 생각했을 때 붙였다 뗐다 할 블럭들의 상대 좌표값을 계산했다. 유형C 같은 경우에는 분홍색으로 표기된 블럭을 추가로 빼줘야 한다.

 

 

제출 코드

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let N, M, countN;
let board = [];

const shapeAdir = [[-1, 0], [-1, 1], [-1, 2], [0, 3], [1, 0], [1, 1], [1, 2]];
const shapeBdir = [[0, -1], [1, -1], [2, -1], [3, 0], [0, 1], [1, 1], [2, 1]];
const shapeCdirPlus = [[-1, 0], [-1, 1], [1, -1], [1, 2]];
const shapeCdirMinus = [[1, 0], [1, 1], [1, 1], [1, 0]];

const checkShapeA = (r, c, smA) => {
  let maxV = smA;
  for (let [dr, dc] of shapeAdir) {
    let nr = dr + r, nc = dc + c;
    if (nr >= 0 && nc >= 0 && nr < N && nc < M) {
      maxV = Math.max(maxV, smA + board[nr][nc]);
    }
  }
  return maxV;
};

const checkShapeB = (r, c, smB) => {
  let maxV = smB;
  for (let [dr, dc] of shapeBdir) {
    let nr = dr + r, nc = dc + c;
    if (nr >= 0 && nc >= 0 && nr < N && nc < M) {
      maxV = Math.max(maxV, smB + board[nr][nc]);
    }
  }
  return maxV;
};

const checkShapeC = (r, c, smC) => {
  let maxV = smC;
  for (let i = 0; i < 4; i++) {
    let [dr, dc] = shapeCdirPlus[i];
    let nr = dr + r, nc = dc + c;
    if (nr >= 0 && nc >= 0 && nr < N && nc < M) {
      let [mr, mc] = shapeCdirMinus[i];
      maxV = Math.max(maxV, smC + board[nr][nc] - board[r + mr][c + mc]);
    }
  }
  return maxV;
};

const solution = (board) => {
  let maxV = 0;

  for (let r = 0; r < N; r++) {
    for (let c = 0; c < M; c++) {
      let maxA = 0, maxB = 0, maxC = 0;

      if (c + 2 < M) {
        let smA = board[r][c] + board[r][c + 1] + board[r][c + 2];
        maxA = checkShapeA(r, c, smA);
      }
      if (r + 2 < N) {
        let smB = board[r][c] + board[r + 1][c] + board[r + 2][c];
        maxB = checkShapeB(r, c, smB);
      }
      if (r + 1 < N && c + 1 < M) {
        let smC = board[r][c] + board[r + 1][c] + board[r][c + 1] + board[r + 1][c + 1];
        maxC = checkShapeC(r, c, smC);
      }
      maxV = Math.max(maxV, maxA, maxB, maxC);
    }
  }
  console.log(maxV);
};

readline
  .on("line", (line) => {
    if (!N) {
      [N, M] = line.split(" ").map(Number);
      countN = N;
    } else {
      board.push(line.split(" ").map(Number));
      countN--;
      if (!countN) {
        solution(board);
        readline.close();
      }
    }
  })
  .on("close", () => {
    process.exit();
  });

 

 

문제 링크

14500번: 테트로미노