문제

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

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

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

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

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

예제 입력 1
4 4
0100
0111
1110
0010

예제 출력 1
4

접근

dp라는 걸 알고 풀어서 그나마 쉽게...도 못 풀었고 결국 챗지피티의 도움을 좀 받았다.
dp라는 것도 몰랐으면 bfs나 dfs로 접근했을 수도 있을 것 같다...

dp[i][j]에 (i, j)를 오른쪽 아래 꼭짓점으로 해서 만들 수 있는 정사각형의 한 변의 길이의 최댓값을 저장한다고 해보자.

이 정사각형의 한 변의 길이를 1씩 늘릴 때마다 위 그림과 같이 가로, 세로, 대각선이 각각 1씩 늘어날 것이다.

그렇다면 결국 dp[i][j]는
1. 가로로 최대한 늘린 길이
2. 세로로 최대한 늘린 길이
3. 대각선으로 최대한 늘린 길이
이 세 가지 중 최솟값이 될 것이다.
(가로, 세로, 대각선이 같은 길이만큼 늘어나야 정사각형이니까.)

이를 바탕으로 점화식을 세워보면
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
가 된다.

구현

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

class Main {
    static int n;
    static int m;
    static char[][] arr;
    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());
        arr = new char[n][m];
        dp = new int[n][m]; // (n, m)을 오른쪽 아래 꼭짓점으로 하여 만들 수 있는 정사각형의 최대 크기
        int answer = 0;
        
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = input.charAt(j);
                if (arr[i][j] == '1') {
                    dp[i][j] = (i == 0 || j == 0)? 1 : Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    answer = Math.max(answer, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }

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

dp로 구현하는 건 어렵지 않았는데 아이디어를 떠올리는 것이 어려웠던 것 같다.