[ 프로그래머스 ] #12905 : 가장 큰 정사각형 찾기 - JAVA

🔗 가장 큰 정사각형 찾기

 

• dp는 해당 위치에서 확장가능한 정사각형의 한 변의 길이를 저장
  • 첫 행, 첫 열은 board 배열과 동일하게 함
• dp[i][j] 을 기준으로 위쪽, 왼쪽, 대각선 위치의 dp에서 가능한 한 변의 길이를 확인
  • 대각선으로 확장되므로 최솟값으로 저장해야 함
  • 이때, 한 변이 증가 되므로 최솟값+1

🔎 점화식

dp[n] = min( dp[i-1][j-1] , dp[i-1][j], dp[i][j-1] ) + 1

class Solution
{
    public int solution(int [][]board)
    {
        int rows=board.length;
        int cols=board[0].length;

        // 최대 한 변의 길이
        int area=0;

        //해당 위치에서 만들 수 있는 정사각형의 한 변의 길이
        int[][]dp=new int[rows][cols]; 

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){

                if(board[i][j]==1){
                    if(i==0 || j==0) {// 첫 행, 첫 열은 그대로 
                        dp[i][j]=board[i][j];
                    }else{
                        // 현재 위치에서 대각선, 위, 왼쪽에서 
                        // 정사각형을 만들 수 있는 최소한의 한 변의 길이 
                        dp[i][j]=Math.min(
                            dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    }

                    // 최대 한 변의 길이 update
                    area=Math.max(area, dp[i][j]);

                }
            }
        }

        // 최대 넓이 반환
        return area*area;
    }
}