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

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

 Input 

4 4

0100

0111

1110

0010

 

 Output 

4 

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

▶ DP[i][j] = (i,j)를 우측 끝으로 하는 정사각형의 최대 크기의 제곱근

DP[i][j]는 map[i][j] = 1인 지점에서 점화식

DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1;

 

map[][]은 『0』과 『1』이므로 min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + map[i][j];라고 표현 가능.

　

DP[i][j] 최대값 = 2이므로 정사각형의 크기는 2×2 = 4

 

---

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
         
        int[][] map = new int[N+1][M+1];
        int[][] DP = new int[N+1][M+1];
         
        for(int i=1; i<=N; i++) {
            String str = sc.next();
            for(int j=1; j<=M; j++) {
                map[i][j] = str.charAt(j-1) - '0';      
            }
        }
         
        int answer = 0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                if(map[i][j] == 1) {
                    DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1;                
                    answer = Math.max(answer, DP[i][j]);
                }
            }
        }
        System.out.println(answer*answer);
    }
 
    private static int min(int A, int B, int C) {
        return Math.min(Math.min(A, B), C);
    }
}