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

문제

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

전략

• 완전탐색 : 입력값이 1000 * 1000 으로 너무커서 안된다
• dp를 통해 접근해보자
  • dp로 접근시 dp[i][j] = 해당좌표 i,j를 기준으로 가장 큰 정사각형의 길이
  • 이때 정사각형 4 꼭지점 중 어떤 점을 i,j 로 둘것인가
  • 오른쪽 아래 꼭지점을 기준으로 했을 때 좌표를 i = 0, j = 0으로 탐색시 작은 사각형부터 탐색할 수 있을것이라고 판단하였다.
  • 따라서 왼쪽 , 위 , 왼쪽 위의 꼭지점이 모두 1이 될 경우 정사각형으로 확장이 가능하다.
  • 아래와 같은 정사각형의 경우 결국 확인해야 하는 세 점 중 최솟값을 기준으로 확장이 가능하다는것을 확인할 수 있다.
    1 1 1 
    1 2 2 
    1 2 3 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
4 4
0000
0110
0110
0000

4 4
1100
1100
0000
0000

4 4 (3%)
0100
0111
1111
0111

4 4
0000
0000
0000
0000

4 4
1111
1111
1111
1111

4 4
1111
1001
1001
1111

4 4
1100
1100
0011
0011

4 5
11000
11100
01111
00111

3 3
000
010
000

3 3 (34%)
000
000
100
* */
public class Back1915_가장_큰_정사각형 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();
    static int N,M;
    static int[][] dp,input;

    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(br.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());
        input = new int[N][M];
        dp = new int[N][M]; // ,i,j를 오른쪽 아래 꼭지점으로 두는 정사각형의 최대 크기
        int max = 0;
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                dp[i][j] = Integer.parseInt(str.charAt(j) + "");
                max = Math.max(max,dp[i][j]);
            }
        }

        for(int i = 0; i < N;i++){
            for(int j = 0; j < M;j++){
                if(dp[i][j] == 1 && i-1>= 0 && j-1 >= 0){
                    int left = dp[i][j-1];
                    int top = dp[i-1][j];
                    int side = dp[i-1][j-1];
                    int min = Math.min(left,top);
                    min = Math.min(min,side);
                    dp[i][j] = min+1;
                    if(max < dp[i][j])max = dp[i][j];
                }
            }
        }
        for(int[] arr : dp){
            System.out.println(Arrays.toString(arr));
        }
        System.out.println(max * max);
    }
}

유의사항

• 3% 반례 ->  처음에 넓이값으로 DP에 저장했던 것을 길이로 수정
• 34%반례 ->  n = 1, m = 1일때 좌표 탐색시 if문을 접근하지 않아 최대값이 갱신되지 않았기에 처음 입력받을 때 max값을 갱신하도록 수정