BOJ 1915 가장 큰 정사각형

https://www.acmicpc.net/problem/1915

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

---

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

---

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

---

예제 입력 1

4 4
0100
0111
1110
0010

예제 출력 1

4

---

코드

약간 난이도 있는 DP 문제는 오랜만에 풀어서 시간이 좀 걸렸다.

dp[i + 1][j + 1] = min(dp[i][j], dp[i + 1][j], dp[i][j + 1]) + 1

위와 같은 점화식으로 문제를 풀었다.

다만, dp[i][j], dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] 중 하나라도 0일 경우 정사각형이 아니기 때문에, 모두 0이 아닐 경우만 성립한다.

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

public class Main {

    static int N;
    static int M;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new int[N][M];

        boolean isExist = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int input = br.read();
                if(input == '1') {
                    dp[i][j] = 1;
                    isExist = true;
                }
            }

            br.readLine();
        }

        // 주어진 2차원 배열에서 1이 1개도 없을 때
        if(!isExist) {
            System.out.println(0);
            return;
        }

        int answer = calculateMaxArea();
        System.out.println(answer);
    }

    static int calculateMaxArea() {
        int maxLength = 1; // 가장 큰 정사각형의 한 변의 길이

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < M - 1; j++) {
                int squareSize = calculateSquareSize(i, j);

                if(squareSize != 0) {
                    dp[i + 1][j + 1] = squareSize + 1;
                    maxLength = Math.max(maxLength, dp[i + 1][j + 1]);
                }
            }
        }

        // 가장 큰 정사각형의 넓이를 반환
        return maxLength * maxLength;
    }

    static int calculateSquareSize(int x, int y) {
        if(dp[x + 1][y + 1] == 0) {
            return 0;
        }

        // 점화식에 따라 정사각형 변의 길이를 계산
        int size = Math.min(dp[x][y], Math.min(dp[x + 1][y], dp[x][y + 1]));

        return size;
    }
}