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

09 Aug 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

1로 채워진 가장 큰 정사각형을 구하는 문제이다.

주어진 0과 1을 이차원배열에 넣고 dp배열을 만들어 채워나간다.

원래 배열의 값이 0이면 dp배열의 값도 0이 되고,

원래 배열의 값이 1이면 dp배열의 [i-1][j], [i][j-1], [i-1, j-1]값을 확인해야 한다.

저 값들 중 가장 작은 값에 1을 더해주면 현재 위치를 끝으로 하는 정사각형의 길이가 된다.

길이의 최댓값을 갱신하며 dp배열을 채우고 넓이를 구해주면 끝.

---

메모리: 27708KB

시간: 332ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    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[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i < n + 1; i++) {
            String line = br.readLine();
            for (int j = 1; j < m + 1; j++) {
                arr[i][j] = line.charAt(j - 1) - '0';
            }
        }

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

        System.out.println(max * max);

    }

}