[programmers] 가장 큰 정사각형 찾기

08 Apr 2023 in Algorithm on Algorithm

https://school.programmers.co.kr/learn/courses/30/lessons/12905

DP로 풀어야하며, 위, 왼쪽, 왼쪽위의 값중 가장 작은 값에 1을 더해준다.

class Solution
{
    public int solution(int [][]board)
    {
        int maxLen = 0;
        int row = board.length;
        int col = board[0].length;

        for(int i = 0; i < row; i++){
            for(int j = 0 ; j < col ; j++){
                if(board[i][j] == 1 && i > 0 && j > 0){
                    board[i][j] = Math.min(
                            Math.min(board[i - 1][j], board[i][j - 1]),
                            board[i - 1][j - 1]
                    ) + 1;
                }
                maxLen = Math.max(maxLen, board[i][j]);
            }
        }

        return maxLen * maxLen;
    }
}