[DFS] 테트로미노

[ericagong]

⭐ 성찰

1. DFS 조기 종료 가능하면 시간 효율성을 위해 종료시키는 조건 추가하기
2. DFS의 특수한 경우(특정 레벨)에 대한 추가 탐색 로직을 부여할 수 있음.

❓ 문제 상황

테트로미노

👨‍💻 문제 해결: DFS

✅ 1차 풀이: DFS + 특수 경우 탐색 추가

1. DFS로 4개의 블록을 선택하는 경우 모두 탐색해 최댓값 모색
2. DFS 종료 시, ㅗ, ㅜ, ㅓ, ㅏ의 경우를 탐색해 최댓값 변경 시 반영
3. 전체 경우에 대한 최댓값 출력

const fs = require("fs");
const inputs = fs.readFileSync("/dev/stdin").toString().split("\n");

const [N, M] = inputs.shift().split(" ").map(Number);
const g = [];
for (let i = 0; i < N; i++) {
  g[i] = inputs.shift().split(" ").map(Number);
}

let v = Array.from({ length: N }, () => new Array(M).fill(false));
const maxs = Array.from({ length: N }, () => new Array(M).fill(-Infinity));

// 상 하 좌 우
const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];
let s = 0;
function dfs(x, y, l) {
  if (l === 4) {
    maxs[x][y] = Math.max(maxs[x][y], s, specialCase(x, y));
    return;
  }

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];

    if (nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1) continue;
    if (v[nx][ny]) continue;

    v[nx][ny] = true;
    s += g[nx][ny];
    dfs(nx, ny, l + 1);
    v[nx][ny] = false;
    s -= g[nx][ny];
  }
}

// ㅗ, ㅜ, ㅏ, ㅓ 의 DFS 불가 케이스 고려
function specialCase(x, y) {
  let score = 0;

  for (let skip = 0; skip < 4; skip++) {
    let temp = g[x][y];

    for (let i = 0; i < 4; i++) {
      if (i === skip) continue;
      const nx = x + dx[i];
      const ny = y + dy[i];

      // 모양 생성 불가하면 0 반환해 제외
      if (nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1) {
        temp = 0;
        break;
      }

      temp += g[nx][ny];
    }

    score = Math.max(score, temp);
  }

  return score;
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    v[i][j] = true;
    s += g[i][j];
    dfs(i, j, 1);
    v[i][j] = false;
    s -= g[i][j];
  }
}

let result = 0;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    result = Math.max(result, maxs[i][j]);
  }
}

console.log(result);

✅ 2차 풀이: DFS 내에 특별 탐색 조건 추가

1. DFS로 4개의 블록을 선택하는 경우 모두 탐색해 최댓값 모색하되, 특정 조건 하에서 추가 탐색
   ⭐ DFS 조기 종료 조건 추가: if(maxs[x][y] >= s + maxVal * (4 - l)) return
2. 전체 경우에 대한 최댓값 출력

const fs = require('fs')
const inputs = fs.readFileSync('/dev/stdin').toString().split('\n')

const [N, M] = inputs.shift().split(' ').map(Number)
const g = []
let maxVal = -Infinity
for(let i = 0; i < N; i++) {
  g[i] = inputs.shift().split(' ').map(Number)
  maxVal = Math.max(maxVal, ...g[i])
}

let v = Array.from({length: N}, () => new Array(M).fill(false))
const maxs = Array.from({length: N}, () => new Array(M).fill(-Infinity))


// 상 하 좌 우
const dx = [0, 0, -1, 1]
const dy = [-1, 1, 0, 0]
let s = 0
function dfs(x, y, l) {
  // DFS 조기 종료 조건 추가
  if(maxs[x][y] >= s + maxVal * (4 - l)) return
  
  if(l === 4) {
    maxs[x][y] = Math.max(maxs[x][y], s)
    return
  }
  
  for(let i = 0; i < 4; i++) {
    const nx = x + dx[i]
    const ny = y + dy[i]

    if(nx < 0 || ny < 0 || nx > N-1 || ny > M-1) continue
    if(v[nx][ny]) continue

    // ㅓ, ㅏ, ㅜ, ㅗ 특수 케이스 고려
    if(l === 2) {
      v[nx][ny] = true
      s += g[nx][ny]
      dfs(x, y, l+1)
      v[nx][ny] = false
      s -= g[nx][ny]
    }

    v[nx][ny] = true
    s += g[nx][ny]
    dfs(nx, ny, l+1)
    v[nx][ny] = false
    s -= g[nx][ny]
  }
}

for(let i = 0; i < N; i++) {
  for(let j = 0; j < M; j++) {
    v[i][j] = true
    s += g[i][j]
    dfs(i, j, 1)
    v[i][j] = false
    s -= g[i][j]
  }
}


let result = 0
for(let i = 0; i < N; i++) {
  for(let j = 0; j < M; j++) {
    result = Math.max(result, maxs[i][j])
  }
}

console.log(result)