[boj] 14500. 테트로미노 (node.js)

문제

[boj] 14500. 테트로미노 (node.js)

• 문제에서 제시된 4칸짜리 테트로미노를 대칭, 회전까지 포함해서 활용할 때, 포함하는 숫자의 총합이 최대가 되게끔 테트로미노를 위치시키려 한다. 이때 위치에 적힌 값의 총합을 구하는 문제다.

풀이

• 문제에서 제시한 테트리미노는 대칭, 회전하는 경우까지 포함한다. 이는 곧 1*1 4칸으로 만들어낼 수 있는 모든 조합과 같다. 따라서 DFS, BFS를 활용해서 4칸짜리 탐색을 구현한다.
• DFS는 visited 배열을 활용해서 4칸이 될 수 있는 경우 그 자리에 적힌 수들의 총합을 갱신한다. 이때 visited 반환하게 되는 경우 visited 여부를 지워줘야 한다는 점에 유의하자.
• BFS는 DFS를 visited 배열을 활용해 구현했기 때문에 만들 수 없는 모양인 'ㅓ' 모양 테트로미노를 확인해보고 결과를 갱신하기 위한 함수다. 상하좌우 네 가지 방향 중 하나의 방향만을 제외하고 모두 거리를 1만큼 전진시킨 후 합을 갱신한다.

전체 풀이

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

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

const solution = () => {
  const [N, M] = input().split(" ").map(Number);
  const dist = 4;
  const arr = [];
  for (let i = 0; i < N; i++) arr[i] = input().split(" ").map(Number);
  let result = 0;
  let visited = [];

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      for (let k = 0; k < N; k++) visited[k] = [];
      visited[i][j] = 1;
      dfs(i, j, 0, arr[i][j]);
      bfs(i, j);
    }
  }
  return result;

  function dfs(r, c, k, sum) {
    if (k + 1 === dist) {
      result = Math.max(result, sum);
      return;
    } else {
      for (let i = 0; i < 4; i++) {
        const nr = r + dir[i][0];
        const nc = c + dir[i][1];
        if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
        if (visited[nr] && visited[nr][nc]) continue;
        if (!visited[nr]) visited[nr] = [];
        visited[nr][nc] = 1;
        dfs(nr, nc, k + 1, sum + arr[nr][nc]);
        visited[nr][nc] = 0;
      }
    }
  }

  function bfs(r, c) {
    for (let i = 0; i < 4; i++) {
      let sum = arr[r][c];
      for (let j = 0; j < 4; j++) {
        if (i === j) continue;
        const nr = r + dir[j][0];
        const nc = c + dir[j][1];
        if (nr < 0 || nc < 0 || nr >= N || nc >= M) break;
        sum += arr[nr][nc];
      }
      result = Math.max(result, sum);
    }
  }
};

let _line = 0;
const input = () => stdin[_line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  console.log(solution());
  process.exit();
});