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

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

 

접근 방법

1. 격자의 크기가 1000 * 1000 이다.
2. 격자를 순환하며 격자의 크기를 탐색하는 방법 -> 3차원 배열로 해결할 수 있지만 10^9이므로 시간초과가 발생한다 따라서 O(n^2) 이하의 알고리즘을 사용해야한다
3. dp를 사용해 현재 현재 정사각형의 크기를 기록하며 최대값을 비교하자
   1. 현재 idx를 (r,c) 라고 할때, (r-1,c-1), (r-1,c), (r,c-1), 값과 (r,c)이 모두 1이면 한 변의 길이가 2인 정사각형이다
   2. 따라서 0인경우는 건너뛴다
   3. 이전 대각선과 이전 행, 열을가지지 않는 0행, 0열은 1을 그대로 기록한다
   4. 이외에는 이전 대각선, 이전 행,열을 검사하고 3위치의 최소값+1 이 현재 idx를 갖는 정사각형의 변의 길이이다
   5. 최대값을 비교하며 갱신한다
4. 크기가 필요하므로 최대값의 제곱을 반환한다.

코드

class Solution{
    public int solution(int [][]board){
        int r = board.length;
        int c = board[0].length;
        int[][] dp = new int[r][c];
        
        int ans = 0;
        for(int i = 0 ; i < r ; i++){
            for(int j = 0 ; j < c ; j++){
                if(board[i][j] == 0) continue;
                if(i == 0 || j == 0) dp[i][j] = 1;
                else{
                    int cur = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1]));
                    dp[i][j] = cur+1;
                }
                ans = Math.max(ans,dp[i][j]);
            }
        }
        return ans*ans;
    }
}