[1915] 가장 큰 정사각형

✔ 가장 큰 정사각형

[백준 1915]

문제 분석하기

가장 큰 정사각형의 넓이를 구하는 것을 가장 큰 정사각형의 한 변의 길이를 구한다는 것과 동일하므로 이를 통해 문제에 접근

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[i][j]는 i, j의 위치를 오른쪽 아래 꼭짓점으로 정하고, 해당 자리에서 그릴 수 있는 가장 큰 정사각형의 변의 길이
2. 점화식을 구함
   • 현재 자리의 원래 값이 1일 때는 위, 왼쪽, 대각선 왼쪽 위의 값 중 가장 작은 값에 1을 더한 값으로 변경
     D[i][j] = MIN(D[i - 1][j - 1], D[i][j - 1], D[i - 1][j]) + 1
   • 원래 값이 0일 경우 그대로 둠
     D[i][j] = 0
3. 점화식으로 D 배열을 채운 후 D 배열 중 가장 큰 값의 제곱을 출력

슈도코드 작성하기

D[i][j] (i, j 위치에서 왼쪽 위로 만들 수 있는 최대 정사각형 길이를 저장하는 배열)
N(배열의 세로 길이)
M(배열의 가로 길이)
max(최댓값 저장하기)
for(i -> 0 ~ N) {
    for(j -> 0 ~ M) {
        D[i][j]의 값이 1이면 자신의 위, 왼쪽, 대각선 위의 값들 중 최솟값 + 1 값을 저장하기
        D[i][j]의 값이 최댓값보다 크다면 최댓값 업데이트
    }
}
정답(최댓값 * 최댓값) 출력하기

코드 구현하기

/**
 * 1915) 가장_큰_정사각형
 */
public class D091_1915 {
    static int N, M;
    static long[][] D;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(배열의 세로 길이)
        N = sc.nextInt();
        // M(배열의 가로 길이)
        M = sc.nextInt();
        // D[i][j] (i, j 위치에서 왼쪽 위로 만들 수 있는 최대 정사각형 길이를 저장하는 배열)
        D = new long[1001][1001];
        // max(최댓값 저장하기)
        long max = 0;
        for (int i = 0; i < N; i++) {
            String line = sc.next();
            for (int j = 0; j < M; j++) {
                D[i][j] = Long.parseLong(String.valueOf(line.charAt(j)));
                // D[i][j]의 값이 1이면
                if (D[i][j] == 1 && i > 0 && j > 0) {
                    // 자신의 위, 왼쪽, 대각선 위의 값들 중 최솟값 + 1 값을 저장하기
                    D[i][j] = Math.min(D[i - 1][j - 1], Math.min(D[i][j - 1], D[i - 1][j])) + D[i][j];
                }
                // D[i][j]의 값이 최댓값보다 크다면
                if (max < D[i][j]) {
                    // 최댓값 업데이트
                    max = D[i][j];
                }
            }
        }
        // 정답(최댓값 * 최댓값) 출력하기
        System.out.println(max * max);
    }
}