이 문제는 주어진 0과 1로 이루어진 2차원 배열에서 1로 이루어진 가장 큰 정사각형의 크기를 구하는 문제입니다. 이 문제를 효율적으로 풀기 위해 동적 계획법(Dynamic Programming)을 사용할 수 있습니다.
문제 풀이
- 우리는 동적 계획법을 사용하여 배열의 각 위치에서 끝나는 가장 큰 정사각형의 한 변의 길이를 계산할 수 있습니다. 이를 위해 dp[i][j]를 사용해 (i,j) 위치에서 끝나는 가장 큰 정사각형의 변의 길이를 저장합니다.
알고리즘
- 주어진 배열의 각 요소를 순회하면서, 해당 요소가 1일 때 그 위치에서 끝나는 가장 큰 정사각형의 변의 길이를 계산합니다.
- 계산하는 방법은 해당 위치의 위쪽, 왼쪽, 왼쪽 대각선 위의 값들을 참고하여 결정합니다. * 만약 현재 위치가 (i, j) 라면, dp[i][j]=min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1 * 만약 현재 위치가 배열의 첫 행이나 첫 열에 있다면, 그 위치에서 만들 수 있는 최대 정사각형의 크기는 그 자체로 1입니다.
- 최종적으로 dp 배열에서 가장 큰 값을 찾고, 그 값을 제곱한 것이 우리가 구하려는 가장 큰 정사각형의 넓이가 됩니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int dp[][] = new int[n][m];
int max = 0;
for (int i = 0; i < n; i++) {
String[] s = sc.next().split("");
for (int j = 0; j < m; j++) {
dp[i][j] = Integer.parseInt(s[j]);
if (dp[i][j] > 0 && i > 0 && j > 0) {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
max = Math.max(max, dp[i][j]);
}
}
System.out.println(max * max);
}
}