[Programmers]-가장 큰 정사각형 찾기

문제

0과1로 된 배열중에서 가장 큰 넓이가 되는 정사각형의 넓이를 반환해라.

코드

class Solution
{
    int max = 0;
    public int solution(int [][]board)
    {
        int answer;
        int m = board.length;
        int n = board[0].length;//m X n

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(board[i][j]==0) continue;
                getMaxValue(board, i, j);
            }
        }
        
        if(m ==1|| n ==1) return 1;
        return max*max;
    }
    public void getMaxValue(int[][] board, int i, int j){

        int up = board[i-1][j];
        int left_up = board[i-1][j-1];
        
        int min = board[i][j-1];//left
        if(min > up) min = up;
        if(min > left_up) min = left_up;
        board[i][j] = ++min;
        
        if(max < min) max = min;
    }
}

코드 설명

[1,1]부터 시작한다.

그리고 현 위치 기준으로 왼,위,왼쪽위의 값 중에서 최소값을 구한다.

max는 가장큰 정사각형의 한변 길이이다.

min은 왼, 위, 왼쪽위의 값 중 최소값이다.

현 위치에 min+1을 넣어준다.

max이 min보다 작으면 max에 min을 넣어준다.

위의 설명은 현위치의 값이 0이 아닐경우에만 해당한다.

요약

• 좀더 쉽게 구해보기.