https://www.acmicpc.net/problem/1915
문제
n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
0 1 0 0
0 1 1 1
1 1 1 0
0 0 1 0
위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.
입력
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.출력
첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.DP문제~!
a[i][j]를 정사각형의 우측하단으로 하는 정사각형의 한변의 길이로합니다.
0 0
0 1 일경우 a[1][1]을 우측하단으로 하는 정사각형일때 최대 변의길이는 a[1][1]을 둘러싸고있는 값들중 가장작은 값+1
즉 a[1][1]==1이 들어가게됩니다.
만약
1 1
1 1 일경우에 a[1][1]은 둘러싸고있는 값들중 가장작은값이 1이기때문에
1 1
1 2 로 변화하게된다 즉 a[1][1]==2가 됩니다.
만약 더 큰수로할때
1 1 1 0
1 1 1 0
1 1 1 0
일 경우에는
1 1 1 0 | 1 1 1 0 | 1 1 1 0 | 1 1 1 0
1 2 1 0 | 1 2 2 0 | 1 2 2 0 | 1 2 2 0
1 1 1 0 | 1 1 1 0 | 1 2 1 0 | 1 2 3 0
으로 변화하면서 a[i][j] 즉 a[2][2]를 우측하단으로
삼는 가장 큰 정사각형의 한변의 길이는 3이됩니다.
해당하는 내용을 코드로 바꾸면
if (a[i][j] != 0)
{
a[i][j] = Math.min(a[i - 1][j - 1], Math.min(a[i - 1][j], a[i][j - 1])) + 1;
}
이런 형태가 됩니다.
다만 이형태를 사용하려면 a[-1][-1]의 값을 읽기때문에
java.lang.ArrayIndexOutOfBoundsException 이 뜬다 즉 배열의 인덱스 범위를 벗어나기때문에
1 1 1 0
1 1 1 0
1 1 1 0 을
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0 형태로 다시 저장을해서 -1 부분의 값을 읽어올 수 있도록 배열의 크기를 바꿔줘야합니다.
소스
package test;
import java.util.*;
class Main {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int arr[][]=new int[n][m];
for(int i=0;i<n;i++) {
String q=sc.next();
for(int j=0;j<m;j++) {
arr[i][j]=q.charAt(j)-'0';
}
}
System.out.println(solution(arr));
}
public static int solution(int [][]board)
{
int answer = 0;
int hang=board.length;
int yeul=board[0].length;
int [][]a=new int[hang+1][yeul+1];
for(int i=0;i<hang;i++) {
for(int j=0;j<yeul;j++) {
a[i+1][j+1]=board[i][j];
}
}
for (int i = 1; i <= hang; i++)
{
for (int j = 1; j <= yeul; j++)
{
if (a[i][j] != 0)
{
a[i][j] = Math.min(a[i - 1][j - 1], Math.min(a[i - 1][j], a[i][j - 1])) + 1;
answer = Math.max(answer, a[i][j]);
}
}
}
return answer*answer;
}
}