[JavaScript/DP] 백준 골드 4 : 1915 - 가장 큰 정사각형

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

---

📌 작성한 코드 

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

const [N, M] = input.shift().split(" ").map(Number);
const board = input.map((str) => str.split("").map(Number));

let answer = 0;
const dp = Array.from({ length: N }, () => new Array(M).fill(0));

const solution = () => {
    if (N === 1 || M === 1) {
        if (board.flat(2).includes(1)) answer = 1;
        else answer = 0;

        return;
    }

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (i === 0 || j === 0) {
                dp[i][j] = board[i][j];
                answer = Math.max(answer, dp[i][j]);
                continue;
            }

            if (board[i][j] === 0) continue;

            const up = dp[i - 1][j];
            const left = dp[i][j - 1];
            const cross = dp[i - 1][j - 1];

            dp[i][j] = Math.min(up, left, cross) + 1;
            answer = Math.max(dp[i][j], answer);
        }
    }
};

solution();

console.log(answer * answer);

 

📌 설명 

점화식 : dp[i][j] : (i, j)값을 포함하는 가장 큰 정사각형의 변의 길이

- (현재 값이 1인 경우에) 현재 인덱스에서 위, 왼쪽, 대각선을 살펴보고 그 중 가장 작은 값 + 1로 업데이트 해주면 된다.

-> 정사각형을 만들려면 위, 왼쪽, 대각선을 모두 살펴봐야 함 -> 그 중에 가장 작은 값을 기준으로 정 사각형을 만들어야 함

-> 가장 작은 값을 기준으로 만들지 않으면 정사각형 범위 안에 0이 있을 수 있기 때문!

 

✅ 성공