[백준] 14500 테트로미노 - javascript

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = input.shift().split(" ").map(Number);
const arr = input.map(i => i.split(" ").map(Number));
const visited = Array.from({ length: n }, () =>
  Array.from({ length: m }, () => 0)
);
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
const ddx = [
  [0, 0, 0, 1],
  [0, 1, 2, 1],
  [0, 0, 0, -1],
  [0, -1, 0, 1],
];
const ddy = [
  [0, 1, 2, 1],
  [0, 0, 0, 1],
  [0, 1, 2, 1],
  [0, 1, 1, 1],
];
let ans = 0;

const dfs = (x, y, sum, cnt) => {
  if (cnt === 4) {
    ans = Math.max(ans, sum);
    return;
  }
  for (let i = 0; i < 4; i++) {
    let [nx, ny] = [x + dx[i], y + dy[i]];
    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

    if (!visited[nx][ny]) {
      visited[nx][ny] = true;
      dfs(nx, ny, sum + arr[nx][ny], cnt + 1);
      visited[nx][ny] = false;
    }
  }
};

const checkNoDfs = (x, y) => {
  for (let i = 0; i < 4; i++) {
    let flag = false;
    let sum = 0;

    for (let j = 0; j < 4; j++) {
      let nx = x + ddx[i][j];
      let ny = y + ddy[i][j];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
        flag = true;
        break;
      } else {
        sum += arr[nx][ny];
      }
    }
    if (!flag) {
      ans = Math.max(ans, sum);
    }
  }
};

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    visited[i][j] = true;
    dfs(i, j, arr[i][j], 1);
    visited[i][j] = false;
    checkNoDfs(i, j);
  }
}

console.log(ans);

✔ 알고리즘 : DFS

✔ 5개의 도형중 ㅜ를 제외하고는 왔던 길을 되돌아 가야하는 상황이 발생하지 않기 때문에 DFS 탐색으로 찾을 수 있다.

✔ ㅜ를 제외한 4가지 경우 👉 DFS
범위를 벗어나지 않고 방문하지 않은 점이면 탐색을 이어나간다. 4개 블록을 탐색했을 때 ans를 갱신하고 return한다.

✔ ㅜ의 경우 👉 브루트포스

const ddx = [
  [0, 0, 0, 1],
  [0, 1, 2, 1],
  [0, 0, 0, -1],
  [0, -1, 0, 1],
];
const ddy = [
  [0, 1, 2, 1],
  [0, 0, 0, 1],
  [0, 1, 2, 1],
  [0, 1, 1, 1],
];

로 ㅜ가 가능한 4개의 모양에서 왼쪽 상단을 (0,0) 기준으로 생각하고 브루트포스 탐색한다.
4개의 모양이 모두 범위안에 있을 때 ans를 갱신한다.

✔ 난이도 : 백준 기준 골드 5