[백준 1915] 가장 큰 정사각형 (자바)

백준 1915번 가장 큰 정사각형 (자바)

 

 

 

출처

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

 

 

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

 

 

 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

 

 

 

출력

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

 

 

 

 

입출력 예

입출력 예 1

 

 

 

걸린 시간

약 2시간..?

DP는 너무 어렵다.

 

 

 

접근 방법

처음에는 현재 위치(i,j)를 기준으로 (i, j-1), (i-1, j)만 검사하면 되는 줄 알고 1인 경우 넓이를 구했지만 어림도 없었다.

1을 발견할 때마다 (i,j-1), (i-1, j), (i-1, j-1) 세 좌표를 모두 검사해 2x2정사각형을 만족했을 때 현재 위치에 한 변의 길이를 넣어주는 식으로 진행했다.

이러한 과정을 계속해가면서 1이거나 1이상의 값들을 만나는 경우 조건을 만족하면 정사각형이므로 변의 길이를 갱신한다.

 

 

 

 

내 코드

 

 

 

고려할 점

1. DP 사용할 것

2. 변의 길이를 이용해 넓이를 구할 것