[LeetCode] 221. Maximal Square

😎풀이

1. dp 배열 초기화
2. 2중 반복을 통해 matrix 순회
   2-1. matrix[i][j]가 1인 경우 탐색
   2-2. 첫 행 혹은 첫 열이라면 matrix[i][j] 에서 끝나는 변의 길이는 항상 1
   2-3. 왼쪽, 윗쪽, 대각선 왼쪽 위 모두 채워져 있어야 하므로 최솟값 탐색 및 + 1한 값을 현재 dp에 적용
   2-4. 최대 길이의 변 갱신
3. 최대 길이 변의 제곱 반환

function maximalSquare(matrix: string[][]): number {
    const m = matrix.length;
    const n = matrix[0].length;
    
    // DP 배열 초기화
    const dp: number[][] = Array(m).fill(0).map(() => Array(n).fill(0));
    let maxSide = 0;
    
    // DP 배열 채우기
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === "1") {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1;  // 첫 번째 행이나 열이라면 정사각형의 크기는 1
                } else {
                    // 정사각형이 1로 채워져야 하므로, 계산된 인접 셀 중 최솟값 + 1
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
                maxSide = Math.max(maxSide, dp[i][j]);  // 가장 큰 한 변 길이 갱신
            }
        }
    }
    
    // 최대 면적 반환
    return maxSide * maxSide;
}