백준 온라인 저지에서 문제를풀어보자 #6(1915번: 가장 큰 정사각형)

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;
}

}