백준 1915 자바 - 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

문제

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

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

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

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int[][] dp;
    private static char[][] board;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
        board = new char[n][m];
        dp = new int[n][m];

        int max = 0;
        for (int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                dp[i][j] = board[i][j] - '0';
                if (dp[i][j] == 1 && max == 0) max = 1;
                if (j > 0 && i > 0) {
                    if (dp[i - 1][j] > 0 && dp[i][j - 1] > 0 && dp[i - 1][j - 1] > 0 && dp[i][j] == 1) {
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                        max = Math.max(dp[i][j], max);
                    }
                }
            }
        }
        bw.write(String.valueOf(max * max));
        bw.flush();
    }
}

풀이

 4칸을 한번에 비교해서 2행과 2열이 있다고 할 때, 2행2열자리에 1이 있을 경우 나머지 칸들의 가장 작은 값에 + 1 하여 저장한다. 이렇게 계속 저장하다 보면 가장 큰 값이 가장 큰 정사각형의 한 변의 길이가 되어 이 값의 제곱을 출력하면 된다.