백준 - 가장 큰 정사각형(1915)

오늘 풀어볼 문제는 ⭐가장 큰 정사각형 입니다.

1. 문제 설명

n*m 테이블은 원소가 0과 1로 구성되어 있다. 1로 모두 채워진 정사각형의 최대 넓이를 구하면 된다.

2. 문제 접근

DP라고 생각했다. (애초에 DP 연습하려고 푼 문제임)
그렇다면 왜 DP라고 판단하는게 제일 적합한가?

1. 단순히 브루트포스로 풀고자 하면 O(N^2 * M^2)가 나오게 됨. 즉 1000^4이라는 의미. ㄷㄷ?
2. 해당 문제는 dp[i][j]을 정의하여, 해당 위치에서 끝나는 가장 큰 정사각형의 한 변의 길이를 저장할 수 있음. 이렇게 되면 이전 인덱스들 기준 최대 길이를 알고 계산에 재활용할 수 있기에 DP라는 결론이 나옴.

3. 풀이

이 문제의 핵심 풀이는, 현재 위치에서 끝나는 가장 큰 정사각형의 한 변 길이를 저장하는 것임.

보기 쉽게 그림으로 정리해보면 다음과 같음

이렇게 하면 N*M번 만에 가장 큰 정사각형의 한 변의 길이를 찾을 수 있음.
그럼 최종적으로는 해당 길이^2만 해주면 끝!!

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int [][] dp = new int[N+1][M+1];
        int [][] arr = new int[N+1][M+1];

        for(int i=1; i<=N; i++) {
            String s = br.readLine();
            for(int j=1; j<=M; j++) {
                char c = s.charAt(j-1);
                arr[i][j]=Integer.parseInt(String.valueOf(c));
            }
        }

        int answer = 0;

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                if(arr[i][j]==0) {
                    dp[i][j]=0;
                    continue;
                }
                dp[i][j]=Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1]))+1;
                answer = Math.max(answer, dp[i][j]);
            }
        }

        System.out.println(answer*answer);
    }
}