백준 14925 목장 건설하기

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

문제

만들 수 있는 가장 큰 정사각형 목장의 크기를 구하는 문제이다. 하나하나 찾을 수 있는 경우를 찾기 위해서는 끝도 없다. 따라서 이 문제는 땅들을 탐색하면서 점차 만들 수 있는 정사각형의 크기를 구해야 하기 때문에 기존에 탐색했던 땅을 활용하여 구해야 최적의 알고리즘이다. 따라서 다이나믹 프로그래밍을 이용해야 한다.

dp 배열 설계

dp는 2차원으로 해당 땅의 크기와 똑같은 배열의 크기로 만들며, dp[i][j]의 값은 해당 위치에서 가질 수 있는 가장 큰 땅의 크기이다.

풀이

먼저 이를 구하는 과정에서 하나 있는 조건은 나무와 바위의 경우 치울 수 없다는 조건이 있다. 따라서 해당 조건에서는 애초에 목장을 지을 수 없는 조건이기 때문에 dp[i][j]의 값을 0으로 한다.

목장을 만들 수 있는 경우에는 이전에 탐색했던 곳 중에서 왼쪽, 대각선 왼쪽, 위쪽 땅에서 목장을 작게나마 건설할 수 있다면 해당 목장을 dp[i][j]에서는 해당 목장을 더 넓힐 수 있는 기회가 주어진다. 하지만 이 모든 땅에서 만족시키는 크기를 찾아야 하므로 세 경우에서 가장 작은 수에 1을 더하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [size, ...maps] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [m, n] = size.split(" ").map(Number);
const land = maps.map((e) => e.split(" ").map(Number));
const dpArr = Array.from({ length: m }, () =>
  Array.from({ length: n }, () => 0)
);
 
for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    if (land[i][j] === 0) {
      if (!j || !i) {
        dpArr[i][j] = 1;
      } else {
        dpArr[i][j] =
          Math.min(dpArr[i][j - 1], dpArr[i - 1][j], dpArr[i - 1][j - 1]) + 1;
      }
    } else {
      dpArr[i][j] = 0;
    }
  }
}
console.log(dpArr);
let max = 0;
for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    max = Math.max(max, dpArr[i][j]);
  }
}
console.log(max);

처음에는 이전의 목장의 크기를 계속해서 확장해간다는 개념으로 왼쪽, 대각선 왼쪽, 위쪽 세 방향이 모두 같을 때에만 확장을 하고 아니면 최솟값에 1을 더하는 방식으로 하려고 했다.

for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    if (land[i][j] === 0) {
      if (!j || !i) {
        dpArr[i][j] = 1;
      } else {
        if (
          dpArr[i][j - 1] === dpArr[i - 1][j] &&
          dpArr[i - 1][j] === dpArr[i - 1][j - 1]
        ) {
          dpArr[i][j] = dpArr[i - 1][j] + 1;
        } else {
          dpArr[i][j] =
            Math.min(dpArr[i][j - 1], dpArr[i - 1][j], 1)
        }
      }
    } else {
      dpArr[i][j] = 0;
    }
  }
}

하지만 dpArr[i][j] = Math.min(dpArr[i][j - 1], dpArr[i - 1][j], 1) 여기서 나는 대각선 위쪽을 고려하지 않았던 실수를 저질렀다. 대각선 위쪽 또한 만들 수 있는 최대한의 목장의 값을 가지고 있는데, 단순하게 0인 경우만 있을 거라고 생각하다 보니 아예 1이랑 비교해서 갱신을 시켜버렸던 점이 패착이었다.

for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    if (land[i][j] === 0) {
      if (!j || !i) {
        dpArr[i][j] = 1;
      } else {
        if (
          dpArr[i][j - 1] === dpArr[i - 1][j] &&
          dpArr[i - 1][j] === dpArr[i - 1][j - 1]
        ) {
          dpArr[i][j] = dpArr[i - 1][j] + 1;
        } else {
          dpArr[i][j] =
            Math.min(dpArr[i][j - 1], dpArr[i - 1][j], dp[i-1][j-1]) +1
        }
      }
    } else {
      dpArr[i][j] = 0;
    }
  }
}

얘도 이런 식으로 고치면 정답으로 뜬다 흑흑 dp 어려웡