BOJ 백준온라인져지 1915 가장 큰 정사각형 풀이

문제 설명

1 로 색칠 된 크기가 가장 큰 정사각형의 크기를 구하면 된다.

1 칸은 1 이다.

풀이

정사각형의 조건 가로, 세로의 길이가 같다.

dp 를 이용해서 풀이하기 위해 맨 위부터 오른쪽으로 가면서 차례대로 밑으로 내려갔다.

현재의 위치에서 왼쪽의 길이와 세로의 길이가 같다면 최소한 맨 왼쪽 위를 제외하고 정사각형이 된다는 조건이다.

그러면 맨 왼쪽 위는 어떻게 검사하냐?

왼쪽 위의 대각선을 보면 된다.

결론적으로는 왼쪽, 위, 대각선 왼쪽 위 중 가장 작은 값 + 1를 해주면 된다.

그리고 넓이를 구하는 문제이니 제곱으로 출력해주면 된다. (정사각형 넓이)

코드

문제

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개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

예제 입력 1 

4 4
0100
0111
1110
0010

예제 출력 1 

4