[백준 1915번] 가장 큰 정사각형 (python)

문제

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

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

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

 

기록

(dp 11일차) 시간을 좀 줄여보고 싶어서 여러가지 해봤는데 다 비슷했다..ㅎ

 

이차원 배열에 (i, j)를 오른쪽 아래 모서리로 갖는 1로 구성된 최대 정사각형의 길이를 저장한다.

 위의 문제의 예시인 경우 다음과 같이 배열에 기록된다. 여기서 max값을 출력하면 1로 구성된 최대 정사각형이 나온다.

0	1	0	0
0	1	1	1
1	1	2	0
0	0	1	0

 

아래와 같은 경우, 이차원 배열의 구성과 최대 정사각형을 구하는 과정을 정리해보았다.

각 칸(i, j)에는 (i, j)를 오른쪽 아래 모서리로 갖는 1로 구성된 최대 정사각형 길이를 저장한다. 

현재 칸인 (i, j)이 1이면 (i-1, j), (i, j-1), (i-1, j-1)의 최솟값에 1을 더해 저장한다.

이차원 배열의 max값이 주어진 입력에서의 1로 구성된 최대 정사각형이다.

 

코드

n, m = map(int, input().split())
dp = [[0]*(m+1) for i in range(n+1)]
_max = 0
for i in range(1, n+1):
    for j, board in enumerate(input(), start=1):
        dp[i][j] = int(board)
        if dp[i][j] :
            dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            _max = max(_max, dp[i][j])
print(_max*_max)

1. (i, j)를 오른쪽 아래 모서리로 갖는 1로 구성된 최대 정사각형 길이를 저장할 이차원 배열 dp를 생성한다.

2. 바깥 반복문은 행, 안쪽 반복문은 열 순서대로 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최솟값+1 인 정사각형 길이를 저장한다.

3. 반복문 돌면서 찾은 가장 큰 정사각형 길이를 두 번 곱하여 넓이를 출력한다.