[백준] 1915 가장 큰 정사각형 - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const [n, m] = input.shift().split(' ').map(Number);
let arr = Array.from({ length: n }, () => Array.from({ length: m }, () => 0));

input.map((i, idx) => (arr[idx] = i.trim().split('').map(Number)));
let dp = arr.map((x) => [...x]);

for (let i = 1; i < n; i++) {
  for (let j = 1; j < m; j++) {
    if (arr[i][j]) dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
  }
}

let ans = 0;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    ans = dp[i][j] > ans ? dp[i][j] : ans;
  }
}
console.log(ans ** 2);

✔ 알고리즘 : DP

✔ arr[i][j]가 0인 경우는 어떠한 경우로도 정사각형을 만들 수 없으므로 continue

✔ 그 외에는 길이가 1이라도 무조건 정사각형을 만들 수 있는 경우

✔ 해당좌표 (i,j) 를 기준으로 왼쪽 , 왼쪽 대각선 위 , 위 이렇게 3칸을 비교해보았다. 3칸을 비교하면서, 가장 작은 값에다가 +1 을 해주면 현재 (i,j) 좌표가 우측 하단에 위치하면서 만들 수 있는 가장 큰 정사각형의 길이이다.

✔ 따라서 점화식은

 if (arr[i][j]) dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;

✔ 난이도 : 백준 기준 골드 4