Intuition

브루트포스 전략부터 생각해보면, 10001000을 탐색하면서 해당 좌표를 기준으로 다시 최악의 경우 10001000을 탐색하면서 정사각형의 크기를 가늠해야 하므로 이 로직으로는 풀어낼 수 없다.

x,y 좌표 순회 자체를 막을 순 없으므로 각 좌표에서 미리 계산된 값을 활용해야 한다는 것인데, 너비를 계산하기 위해 먼저 떠오른 방법은 누적합이다. 하지만 누적합으로는 '정사각형'만을 계산하기 어렵다.

그렇다면 미리 계산된 값을 활용하는 로직으로 남은 건 DP뿐이다. 각 좌표 기준으로 최대 정사각형 크기를 알 수 있도록 값을 계산해두고 이를 활용하면 된다.

Algorithm

dp 배열에는 (y,x) 좌표별 최대 정사각형의 변의 길이를 tabulation으로 저장해둔다. 이를 끝까지 수행한 뒤, 다시 dp 완탐을 통해 답을 도출한다.

• f(y,x) = min((y-1,x), (y,x-1), (y-1,x-1))+1

N, M = map(int, input().split())
dp = [[int(i) for i in input()] for _ in range(N)]
for i in range(1,N):
    for j in range(1,M):
        if dp[i][j] >= 1:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
ans = 0
for i in range(N):
    for j in range(M):
        ans = max(ans, dp[i][j])
print(ans*ans)

Complexity Analysis

• time complexity : O(N^2)
• space complexity : O(N^2)