[JAVA] 백준 가장 큰 정사각형 1915

 

가장 큰 정사각형을 구하기 위해서는 BFS를 통해서 찾을 수도 있겠지만 n,m이 최대 1000이기때문에

시간내에 가장 큰 BFS를 찾는 것은 불가능할 것이다.

따라서 다이나믹 프로그래밍을 사용해야한다.

해당 2차원배열에서 가장큰 정사각형을 찾을때

dp[y][x] x는 정사각형 오른쪽 아래에 값으로 현재 정사각형의 최대 크기를 나타낸다.

 dy[y-1][x-1], dy[y-1][x], dy[y][x-1] 에서 가장 작은것에 +1 한것이 dy[y][x]임을 알 수 있다.

 

 

// Online Java Compiler
// Use this editor to write, compile and run your Java code online
import java.util.*;
import java.io.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[][] board = new int[n][m];
        for(int i =0; i<n; i++){
           board[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        }
        int answer = 0;
        for(int i =0; i<m; i++){
            if(board[0][i] ==1){
                answer = 1;
                break;
            }
        }
        for(int i =0; i<n; i++){
            if(board[i][0] ==1){
                answer = 1;
                break;
            }
        }
        
        for(int i =1; i<n; i++){
            for(int j =1; j<m; j++){
                if(board[i][j] != 0){
                    int a = board[i-1][j-1];     
                    int b = board[i-1][j];
                    int c = board[i][j-1];
                    if(a == 0 || b== 0 || c == 0){
                        continue;
                    }
                    board[i][j] = Math.min(a, Math.min(b,c)) +1;
                    answer = Math.max(Math.max(1,answer), board[i][j]);
                }
                
            }
        }
        bw.write(answer * answer + "");
        bw.flush();
        bw.close();
        br.close();
        
    }

    
    
}