[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. 전체 경우에 대한 최댓값 출력
```javascript
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)