문제
- NxM의 0, 1로 된 배열에서 1로 된 가장 큰 정사각형의 크기 구하기
- 1 <= N, M <= 1000
풀이
- dp[i][j] : (i, j)를 포함해 만들 수 있는 1로 된 가장 큰 정사각형의 크기
- i = j = 3 이고 (3, 3) 위치의 값이 1일 때, 정사각형의 최대 크기가 3이 되려면 모든 값이 1이어야 한다.
즉, dp[2][2] = dp[2][3] = dp[3][2] = 2로 모두 동일해야만 한다. 만약 하나라도 2가 아니라면 모든 값이 1이 아니라는 의미가 된다.
예제에서 보면 dp[2][2] = dp[2][3] = dp[3][2] = 1 로 적어도 (2, 2) (2, 3) (3, 2)는 모두 1의 값을 가지기 때문에 최대 2 크기의 정사각형을 만들 수 있다.
- i = 4 / j = 3
dp[3][2] = 1, dp[3][3] = 2, dp[4][2] = 0 이므로 (4, 3) 위치를 포함해 만들 수 있는 정사각형의 크기는 최대 1이 된다. (4, 3)위치의 값이 1이면 1이 되고, 0이면 0이 될 것이다.
N, M = map(int, input().split())
board = [list(map(int, input())) for _ in range(N)]
# dp[i][j] : (i, j)를 포함해 만들 수 있는 1로 된 가장 큰 정사각형의 크기
dp = [[0]*(M+1) for _ in range(N+1)]
answer = 0
for i in range(1, N+1) :
for j in range(1, M+1) :
if board[i-1][j-1] == 1 :
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
answer = max(answer, dp[i][j])
else :
dp[i][j] = 0
print(answer ** 2)
References
