14500. 테트로미노

최근 코딩테스트에서 이 테트로미노와 비슷한 문제를 접했다.

백준에서 문제를 찾아보니 비슷한 문제들이 몇개 있어서 풀어보자!

탐색을 한다고 했을 때 처음 블록을 깊이 1 두번째 블록을 깊이 2라고해보자. 깊이 2에서는 탐색 방법 살짝 다르다.

ㅗ 모양 같은 경우는 탐색하려면 아래와 같이 해야한다. 그냥 무작정 전진해버리면 ㅗ 모양은 탐색할 수 없다.

N,M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
ans = 0
dx,dy = [0,1,0,-1],[1,0,-1,0]
visited = [[0]*M for _ in range(N)]
max_value = max(map(max,board))
def dfs(x,y,dep,_sum):
    global ans
    if dep == 4:
        ans = max(ans,_sum)
        return
    if ans > _sum + max_value*(4-dep):
        return
    for i in range(4):
        nx,ny = x+dx[i], y+dy[i]
        if 0<=nx<N and 0<=ny<M and not visited[nx][ny]:
            visited[nx][ny] = 1
            if dep == 2:
                dfs(x,y,dep+1,_sum+board[nx][ny])
            dfs(nx,ny,dep+1,_sum+board[nx][ny])
            visited[nx][ny] = 0
for i in range(N):
    for j in range(M):
        visited[i][j] = 1
        dfs(i,j,1,board[i][j])
        visited[i][j] = 0
print(ans)

다음은 자바스크립트 풀이입니다.

const fs = require("fs")
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n")
const [n, m] = input[0].split(" ").map(Number)
const visited = Array.from({ length: n }, () =>
  Array.from({ length: m }, () => false)
)
const dx = [0, 0, 1, -1],
  dy = [1, -1, 0, 0]
let [_, ...board] = input
let ans = 0,
  maxValue = 0
board = board.map((e) => e.split(" ").map((e) => +e))
board.map((e) =>
  e.map((ee) => {
    if (ee > maxValue) {
      maxValue = ee
    }
  })
)
function dfs(x, y, dep, sum) {
  if (dep == 4) {
    ans = Math.max(ans, sum)
    return
  }
  if (maxValue * (4 - dep) + sum <= ans) return
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i],
      ny = y + dy[i]
    if (0 <= nx && n > nx && 0 <= ny && ny < m && !visited[nx][ny]) {
      visited[nx][ny] = true
      if (dep === 2) dfs(x, y, dep + 1, sum + board[nx][ny])
      dfs(nx, ny, dep + 1, sum + board[nx][ny])
      visited[nx][ny] = false
    }
  }
}
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    visited[i][j] = 1
    dfs(i, j, 1, board[i][j])
    visited[i][j] = 0
  }
}
console.log(ans)