백준 테트로미노 14500 javascript

14500번: 테트로미노

풀고 찾아보니 하드코딩 느낌으로 푼 사람도 많았다.

하드코딩이 시간 단축이 더 된거보면 하드코딩이 더 나을때도 있더라

 

전형적인 브루트포스 문제이다.

자세한건 코드보면서!!

const fs = require("fs");
const stdin = (
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString()
    : `4 5
    1 2 3 4 5
    1 2 3 4 5
    1 2 3 4 5
    1 2 3 4 5`
).split("\n");

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [N, M] = input()
  .split(" ")
  .map((v) => +v);

const arr = [];
for (let i = 0; i < N; i++) {
  arr.push(
    input()
      .trim()
      .split(" ")
      .map((v) => +v)
  );
}

// 상하좌우 방향
const arrows = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];

// 유효한 값인지 확인 
const isValid = (x, y) => 0 <= x && x < N && 0 <= y && y < M;

// 방문했는지 확인하는 배열
const visited = new Array(N).fill(null).map((_) => new Array(M).fill(false));

let max = 0;

const dfs = (x, y, sum = 0, count = 0) => {
  // 4개일때 탈출 조건
  if (count === 4) {
    if (sum > max) max = sum;
    return;
  }
  for (let [xx, yy] of arrows) {
    const [xxx, yyy] = [x + xx, y + yy];
    
    // isValid => xxx,yyy 위치가 배열에 존재하는지 확인
    // visited 배열 방문했는지 확인
    if (isValid(xxx, yyy) && visited[xxx][yyy] === false) {
    
      
      visited[xxx][yyy] = true;
      dfs(xxx, yyy, sum + arr[xxx][yyy], count + 1);
      visited[xxx][yyy] = false;
    }
  }
};

// ㅗ(욕아님) 모양은 dfs로 체크할 수 없기에 따로 4방향 체크를 해줬다.
const searchList = [];
for (let i = 0; i < arrows.length; i++) {
  const newArrows = [...arrows];
  newArrows.splice(i, 1);
  searchList.push(newArrows);
}

// 위에서 만든 ㅗ모양 체크 리스트로 체크
const checker = (x, y) => {
  for (let searchArrows of searchList) {
    let sum = arr[x][y];
    for (let [xx, yy] of searchArrows) {
      const [xxx, yyy] = [x + xx, y + yy];
      if (!isValid(xxx, yyy)) break;
      sum += arr[xxx][yyy];
    }
    if (sum > max) max = sum;
  }
};

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    // ㅗ 제외한 나머지 체크
    dfs(i, j);
    
    // ㅗ 모양 체크
    checker(i, j);
  }
}

console.log(max);