백준 1915 : 가장 큰 정사각형 (DP)

이번 문제는 좀 어려웠다. (블로그 찾아보면서 했음.)

일단 지금까지 했던 것처럼 복잡도를 확인해보자.
이 문제를 봤을 때 딱 떠오른 방법은,
2 by 2 window sliding을 min(N, M)-1 번 진행하면 된다. 2 x 2 window 해당하는 위치 모두 1이라면 1. (주어진 ground의 크기를 점점 줄여가며.)
하지만 이렇게 하려면 3중 포문 사용해야한다. (sliding window 자체에 이중포문 * min(N, M)-1번)

주어진 Input이 가장 클 때를 생각해보면 1000^3d의 연산이 필요한데, 파이썬은 초당 2000만번 정도 연산이 가능하니 터무니없이 복잡도가 높음을 알 수 있다. 그래서 DP스러운 방법을 찾아야한다.

코드만 첨부한다.

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

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0
위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.
"""
N, M = 4, 4
ground = [[0,1,0,0],
          [0,1,1,1],
          [1,1,1,0],
          [0,0,1,0]]
dp = [[0] * M for _ in range(N)]
dp[0] = ground[0]
for i in range(1, N):
    dp[i][0] = ground[i][0]


"""
    2 by 2 window sliding을 min(N, M)-1 번 진행하면 된다.
    2 x 2 window 해당하는 위치 모두 1이라면 1. (주어진 ground의 크기를 점점 줄여가며.)
    이렇게 하려면 3중 포문 사용해야한다. sliding window 자체에 이중포문 * min(N, M)-1번
    
    시간 제한 2초. 1<=N,M <= 1000이다. -> 2000만 돌아가는데 1초. 1000**3 -> 훨씬 넘는다. 이걸로 진행하면 안된다.
    
    DP를 활용하자. 작은 문제 2x2 -> 3x3 부터 생각.
    현재 위치가 1 일 때만 수행. 정사각형의 나머지 부분이 모두 1이면 됌.
    근데 3x3으로 넘어가서 2x2일 때 정사각형이었다고 판단한 부분을 표시하면 이전 경로 모두 정사각형임이 보장됌. -> 이거 사용하자.
"""

def f():
    for i in range(1, N):
        for j in range(1, M):
            if ground[i][j]==1 :
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

f()


temp = 0
for d in dp:
    temp = max(max(d), temp)
print(temp**2)