백준 1915번 - 가장 큰 정사각형

문제

백준 1915번 - 가장 큰 정사각형

아이디어

• dp[x][y]를 (x, y) 위치를 정사각형의 오른쪽 아래 꼭짓점으로 보고 가능한 최대 한변의 길이라고 가정한다. 그리고 오른쪽 아래 방향으로 탐색한다.
• dp[x][y]가 1이면 정사각형이 가능한 것이다. 그러면 왼쪽과 위쪽, 왼쪽 위 대각선 값을 확인하여 가장 작은 값에 +1 한 값을 저장한다.
• 가장 작은 값인 이유는 만약 하나라도 0이 있으면 정사각형이 아니므로 그대로 1이 될 것이고, 세개 모두 1 이상이라면 최소 변의 길이로만 정사각형이 가능하기 때문이다.
• 이렇게 구한 값중 최댓값^2이 가장 큰 정사각형의 넓이이다.
  (dp[x][y]를 왼쪽 위 꼭짓점으로 보고 해결할 수도 있는데 이때는 왼쪽 위 방향으로 탐색해야 한다.)

예상 시간 복잡도

• 예상 시간 복잡도 : O(N x M)

코드 구현

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

public class BJ_1915 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                dp[i][j] = Character.getNumericValue(s.charAt(j));
            }
        }

        int max = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dp[i][j] == 1 && i > 0 && j > 0) {
                    dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
                }

                max = Math.max(max, dp[i][j]);
            }
        }

        System.out.println(max * max);
    }
}