[백준]#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(다이나믹 프로그래밍) 알고리즘을 이용해서 풀었다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        int[][] map = new int[N+1][M+1];
        int max = Integer.MIN_VALUE;

        for(int i=0; i<N; i++) {
            String input = br.readLine();
            for(int j=0; j<M; j++) {
                map[i+1][j+1] = input.charAt(j) - '0';
            }
        }

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                if(map[i][j] != 0) {
                    int min = Integer.MAX_VALUE;

                    if(min>map[i-1][j])
                        min = map[i-1][j];
                    if(min>map[i][j-1])
                        min = map[i][j-1];
                    if(min>map[i-1][j-1])
                        min = map[i-1][j-1];

                    map[i][j] = min+1;

                    if(max<map[i][j])
                        max=map[i][j];
                }
            }
        }

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