문제
분석
M x N 크기의 땅이 있을 때, 땅에서 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기를 구하는 문제이다. 0은 들판, 1은 나무 그리고 2는 돌을 의미한다.
이 문제는 0으로 된 가장 큰 정사각형의 한 변의 크기를 구하는 문제이다.
하지만 문장 그대로 탐색을 했다가는 M, N이 각각 최대 1000이기 때문에 시간복잡도에서 걸릴 것이다.
따라서 2차원에서의 누적합을 구해서 합이 0이 되는 경우에 한 변을 mx(최종 정답)와 비교하여 갱신시켜주는 방법을 생각했다.
먼저 2차원 배열에서 누적합은 다음과 같이 구한다.
-
누적합 배열
계산을 용이하게 하기 위해 제로 패딩으로 초기화 한다.
그리고 왼쪽에서 온 값, 한 칸 위에서 온 값, 현재 참조하는 위치의 grid값 (코드에서는 인덱스를 맞추기 위해 -1씩 해줌)을 더하고 중복으로 더해진 prefix[i-1][j-1]은 빼준다. -
누적합 구하기
(i, j)부터 (x, y)까지를 구한다 하면,
prefix[x][y] - prefix[x][j-1] - prefix[i-1][y] + prefix[i-1][j-1] 가 된다.
prefix[i-1][j-1]은 중복으로 빼지는 값이므로 더해준다.
이 문제에서는 정사각형이므로 i, j에서 각각 k를 더해준 위치까지를 고려하면 된다.
k의 범위는 i와 j가 뻗어나갈 수 있는 최대 길이 중 더 작은 것을 택한다. (정사각형 이므로)
그리고 시간을 줄이기 위해 mx부터 시작한다. mx보다 작으면 계산할 이유가 없다.
누적합 구하는 공식으로 val에 값을 대입했을 때 val이 0이면 mx를 갱신한다.
0이 아니라면 더 큰 사각형은 고려할 필요가 없으므로 break한다.
코드
해결언어 : Python
import sys
input = sys.stdin.readline
m, n= map(int, input().split())
grid = [
list(map(int, input().split()))
for _ in range(m)
]
prefix = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
prefix[i][j] = prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+grid[i-1][j-1]
mx = 0
for i in range(1, m+1):
for j in range(1, n+1):
for k in range(mx, min(n-j, m-i)+1):
val = prefix[i+k][j+k]-prefix[i+k][j-1]-prefix[i-1][j+k]+prefix[i-1][j-1]
if not val:
mx = max(mx, k+1)
else:
break
print(mx)
끝으로..
누적합을 적용한 문제를 풀어봤는데, 시간을 줄이는 것이 생각보다 빡빡했다.
