[ BOJ ][JAVA][1915] 가장 큰 정사각형

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	23926	7401	5290	29.285%

문제

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

*/
import java.io.*;
import java.util.*;
public class p1915 {
    static int n, m;
    static long max = 0;
    static int[][] arr, 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 + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            String line = br.readLine();
            for (int j = 1; j <= m; j++) {
                int temp = line.charAt(j-1)-'0';
                // 좌표가 1인 정사각형만 모아야 하므로 0일 때는 구간합을 수행하지 않는다.
                if (temp == 1) {
                    dp[i][j] = Math.min(dp[i-1][j-1] , Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        System.out.println(max * max);

    }
}