[백준 14500 - Node.js] 테트로미노

🔗 문제 링크

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

✏️ 풀이

const [[N, M], ...paper] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(v => v.split(' ').map(Number));

const maxValue = paper
  .reduce(
    (acc, row) => 
    	Math.max(acc, row.reduce((acc, v) => Math.max(acc, v), 0)),
    0
  );
const offset = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const visited = [...Array(N)].map(() => Array(M).fill(false));
let maxSum = 0;

const dfs = (x, y, count, sum) => {
  if (sum + (4 - count) * maxValue <= maxSum) {
    return;
  }

  if (count === 4) {
    maxSum = Math.max(maxSum, sum);
    return;
  }

  for (const [dx, dy] of offset) {
    const nx = x + dx;
    const ny = y + dy;
    if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {

      if (count === 2) {
        visited[nx][ny] = true;
        dfs(x, y, count + 1, sum + paper[nx][ny]);
        visited[nx][ny] = false;
      }

      visited[nx][ny] = true;
      dfs(nx, ny, count + 1, sum + paper[nx][ny]);
      visited[nx][ny] = false;
    }
  }
};

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    visited[i][j] = true;
    dfs(i, j, 1, paper[i][j]);
    visited[i][j] = false;
  }
}

console.log(maxSum);

테트로미노 각 도형의 모양은 ㅗ, ㅓ, ㅏ, ㅜ 모양을 제외하고는 모두 DFS로 4번 탐색해서 나오는 모든 경우와 같다. ㅗ, ㅓ, ㅏ, ㅜ의 경우 DFS를 세 번 시행한 후에 ㅣ, ㅡ, ㄴ, ㄱ 와 같은 모양이 되므로 여기서 절대로 DFS로는 이동경로가 ㅗ, ㅓ, ㅏ, ㅜ가 되도록 이동할 수 없다. 따라서 DFS로 4번 탐색하여 나오는 모든 경우 + ㅗ, ㅓ, ㅏ, ㅜ인 경우에 대해서 최댓값을 구하면 된다.

 

종이 위의 모든 좌표에 대해 DFS를 하여 모든 경우를 탐색한다. 탐색을 4번째 할 때마다 기존의 합의 최댓값과 비교하여 갱신한다. 탐색을 2번째 할 때마다 추가로 DFS를 한 번 더 실행하는데, 이 때 세 번째로 이동할 좌표를 탐색한 것으로 간주(visited[nx][ny] = true)하고 그냥 원래의 좌표(x, y)에서 다시 DFS를 실행한다. 이렇게 하면 두 개의 좌표만 탐색한 상태에서 두 번째 좌표에서 이동할 수 있는 4방향 중 한 곳을 방문 처리 후, 다른 좌표를 탐색하게 되는데 이렇게 하면 한 좌표에서 두 개의 방향을 탐색하면서 자연스럽게 ㅗ, ㅓ, ㅏ, ㅜ 모양을 커버할 수 있게 된다.

 

DFS가 수행시간이 오래 걸리므로 최적화를 위해 미리 종이 위의 좌표에 적힌 숫자 중 최댓값을 구하고, 매 DFS마다 앞으로 남은 탐색해야 할 좌표가 모두 이 최댓값이라고 가정했을 때 maxSum을 갱신할 수 있는지 여부(sum + (4 - count) * maxValue <= maxSum)를 먼저 판단하여 불가능하다고 판단되면 미리 DFS를 중단시키도록 하였다. 이렇게 하니까 수행시간이 2.5배 이상 빨라졌다.