[프로그래머스/Java] 가장 큰 정사각형 찾기

-Code

class Solution {
    public int solution(int[][] board) {
        int rowSize = board.length;
        int colSize = board[0].length;
        int maxSize = 0;
        // dp 셋팅 및 계산
        int[][] dp = new int[rowSize][colSize];
        // dp로 크기 계산
        for(int row = 0; row < rowSize; row++) {
            for(int col = 0; col < colSize; col++) {
                // 첫 행이나 첫 열은 값 셋팅
                if (row == 0 || col == 0) {
                    dp[row][col] = board[row][col];
                } else if (board[row][col] == 1) {
                    // 위, 왼쪽위, 왼쪽 3개중 최소값 찾기
                    // 이 3개의 값이 존재해야 해당 크기 계산이 가능
                    int minVal = Math.min(
                            dp[row - 1][col],
                            Math.min(dp[row -1][col - 1], dp[row][col - 1])
                    ) + 1;
                    dp[row][col] = minVal;
                }
                // 최대 크기면 저장
                maxSize = Math.max(maxSize, dp[row][col]);
            }
        }
        return maxSize * maxSize;
    }
}

처음에 쉽게 완전 탐색으로 하려다가 시간 초과 문제가 생길 거 같아서 고민하다가 생각이 안 나 힌트를 찾아보니 dp문제였습니다. 결국 첫 행과 첫 열을 빼고 1인 경우 왼쪽, 왼쪽 위, 위의 값의 최솟값이 1 이상이면, 이전에 존재한 dp값의 최소보다 1이 큰 크기이므로 이를 통해 해결할 수 있었습니다.