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

class Solution
{
    int[][] board;
    int[][] check;
    int row, column, answer;
    public int solution(int [][]board)
    {
        this.board = board;
        answer = 0;
        row = board.length;
        column = board[0].length;
        check = new int[row][column];
        refreshSquare();
        checkSquare();
        answer = answer * answer;
        return answer;
    }

    void refreshSquare(){
        for(int i = 0; i < row; i++){
            int point = 0;
            for(int j = column-1; j > -1; j--){
                if(board[i][j] == 1){
                    point += 1;
                    check[i][j] = point;
                }else{
                    point = 0;
                }
            }
        }
    }

    void checkSquare(){
        for(int i = 0; i < row; i++){
            for(int j = 0; j < column; j++){
                int num = check[i][j];
                if(num > answer){
                    for(int k = i; k < i + num; k++){
                        if(num < answer)
                            break;
                        if(k == row){
                            num = k - i;
                            break;
                        }
                        if(check[k][j] < num){
                            num = check[k][j];
                        }
                    }
                    if(answer < num){
                        answer = num;                        
                    }
                }
            }
            if(row - i < answer)
                break;
        }
    }

}

 

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int row = board.length;
        int column = board[0].length;
        for(int i = 1; i < row; i++){
            for(int j = 1; j < column; j++){
                if(board[i][j] == 1)
                    board[i][j] = Math.min(Math.min(board[i-1][j], board[i][j-1]), board[i-1][j-1])+1;
            }
        }
        
        for(int i = 0; i < row; i++){
            for(int j = 0; j < column; j++){
                if(answer < board[i][j])
                    answer = board[i][j];
            }
        }
        answer = answer * answer;
        return answer;
    }
}

 

몇주전에 풀었던 거리 기억이 잘 안난다... 나중에 다시풀어보면 설명올리겠다.