[백준] 1915* 가장 큰 정사각형 (골드4)

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

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

public class Main {
    // 동, 남, 남동
    static int[] dx = {0,1,1};
    static int[] dy = {1,0,1};
    static char[][] arr;
    static int n,m;
    public static void main(String[] args) throws Exception {
        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];
        for(int i=0;i<n;i++){
            String s = br.readLine();
            for(int j=0;j<m;j++){
                arr[i][j] = s.charAt(j);
            }
        }

        int max = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]=='1'){
                    max = Math.max(max,bfs(i,j));
                }
            }
        }

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

    static int bfs(int x, int y){
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{x,y});
        int size = 1;

        while(!q.isEmpty()){
            int[] c = q.poll();
            int cnt = 0;

            for(int d=0;d<3;d++){
                int nx = c[0] + dx[d];
                int ny = c[1] + dy[d];

                if(nx<0||nx>=n||ny<0||ny>=m) continue;
                if(arr[nx][ny]=='0') break;
                cnt++;
            }

            if(cnt==3 && x+1<n && y+1<m){
                q.add(new int[]{x+1,y+1});
                size++;
            }
        }
        return size;
    }
}

메모리 초과 및 아이디어 잘못됨. 2*2일때만 가능한 거임
=>
dp 방식으로 변경

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

public class Main {
    static int[][] arr = new int[1001][1001];
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int sqrtAns = 0;
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for (int y = 1; y <= n; y++) {
            String line = br.readLine();
            for (int x = 1; x <= m; x++) {
                arr[y][x] = line.charAt(x-1) - '0';
            }
        }
        for (int y = 1; y <= n; y++) {
            for (int x = 1; x <= m; x++) {
                if (arr[y][x] != 0) {
                    arr[y][x] = Math.min(arr[y-1][x], arr[y][x-1]);
                    arr[y][x] = Math.min(arr[y][x], arr[y-1][x-1]) + 1;
                    sqrtAns = Math.max(arr[y][x], sqrtAns);
                }
            }
        }

        System.out.println(sqrtAns * sqrtAns);

        br.close();
    }
}