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

문제

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다.
표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
가 있다면 가장 큰 정사각형은

1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

풀이

처음은 완전탐색을 생각했다.
그러나 완전탐색으로 길이들을 모두 파악하는 것은 불가능해 보였고, 각 행별로 탐색을 하기로 하였다.
행별로 길이를 파악하여 가로 세로의 길이를 파악하려 했는데 시작과 끝 인덱스의 일치여부도 필요했고, 방문처리도 해야했기에
구현이 쉽지 않았다.
도저히 다른 방법이 생각나지 않아 다른 블로그를 참고하였다.
https://soobarkbar.tistory.com/164
dp는 규칙이 있는 것에 횟수를 누적할 때 사용하는 것으로 알고 있었지만 이를 DP를 활용하여
길이를 구하는 것이 놀라웠다.
DP의 한정적인 생각은 깨는 게기가 되었다..

import java.util.*;
import java.lang.*;

class Solution {
    public int solution(int [][]board) {
        int answer = 0;
        int[][] dp = new int[board.length + 1][board[0].length + 1];

        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                dp[i + 1][j + 1] = board[i][j];
            }
        }

        for (int i = 1; i <= board.length; i++) {
            for (int j = 1; j <= board[0].length; j++) {
                if (dp[i][j] != 0) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }

        return answer * answer;
    }
}