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

문제보기

이쯤되면 DP로 못푸는 문제가 있긴한건가 싶다(…)

핵심이 되는 개념은 이렇다. d[i][j] 를 i,j위치를 우측하단 끝으로 하는 가장 큰 정사각형의 변의길이라고 칠 때, map[i][j] == 1 이면
d[i][j] = min(d[i-1][j-1], d[i-1][j], d[i][j-1]) + 1
이 된다.

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

class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };

     public static void main(String[] args) throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
         StringTokenizer st = new StringTokenizer(br.readLine());
         int n = ip(st.nextToken());
         int m = ip(st.nextToken());
         int[][] map = new int[n][m];
         for(int i = 0 ; i < n ; i++ ) {
        	 String s  = br.readLine();
        	 for(int j = 0 ; j < m ; j++) {
        		 map[i][j] = s.charAt(j)- '0';
        	 }
         }
		
         int[][] d = new int[n][m];
         int max = 0;
         
		// 첫번째행과 첫번째열은 예외처리를 해줘야 한다 
         for(int i = 0 ; i < n ; i++) {
        	 if(map[i][0] == 1) {
        		 d[i][0] = 1;
        		 max = 1;
        	 }
         }
         for(int j = 0 ; j < m ; j++) {
        	 if(map[0][j] == 1) {
        		 d[0][j] = 1;
        		 max = 1;
        	 }
         }
         
         
         // 나머지값도 찾아준다 
         for(int i = 1 ; i < n ; i++) {
        	 for(int j = 1 ; j < m ; j++) {
        		 if(map[i][j] == 1) {
        			 d[i][j] = Math.min(d[i-1][j-1], Math.min(d[i-1][j],  d[i][j-1])) + 1;
        			 if(d[i][j] > max ) max = d[i][j];
        		 }
        	 }
         }
         
         System.out.println(max*max);
     }
}