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

 

작년에 카카오 모의테스트에서 이와 똑같은 문제가 나온적이 있었다.

당시에 dp 문제를 하나도 풀 줄 몰랐는데 신기하게도 이건 술술 풀렸다;;

 

1. 입력받은 대로 2차원 배열을 채운다.

2. 정사각형의 조건을 만족하려면 가로, 세로의 길이가 같고 인접한 배열을 모두 1이어야 하므로

   좌측 위, 좌측, 위의 값이 모두 1 이상이어야 한다.

3. 메모이제이션 기법으로 큰 정사각형의 크기를 누적시키며 진행한다.

 

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

2번을 풀어쓰면 위 식과 같겠다.

 

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int a[][] = new int[n+1][m+1];
        for(int i=1; i<=n; i++) {
            String s = br.readLine();
            for(int j=1; j<=m; j++)
                a[i][j] = s.charAt(j-1) - '0';
        }
        
        int max = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(a[i][j] != 0) {
                    a[i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1]) + 1;
                    max = Math.max(max, a[i][j]);
                }
        
        System.out.println(max*max);
    }
    
    public static int min(int a, int b, int c) {
        int min = a < b ? a : b;
        return min = min < c ? min : c;
    }
}