[백준] 1915번 : 가장 큰 정사각형

해당 문제는 다이나믹 프로그래밍 문제로 해결 합니다. 어떠한 위치 i,j에서 크기 S의 정사각형을 찾는다고 한다면

(i-1)(j-1), (i-1)(j), (i)(j-1) 가 이미 크기가 S인 정사각형이고 (i ,j)가 1인경우에 정사각형입니다. 따라서 작은 크기의 정사각형부터 구해나가면서 가능한 정사각형의 크기를 구합니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
map = [input()[:-1] for _ in range(N)]

square = 0

chk = [[0] * M for _ in range(N)]
for y in range(N):
    for x in range(M):
        if (y == 0 or x == 0) and map[y][x]=='1':
            chk[y][x] = 1
        elif y>=1 and x>=1:
            chk[y][x] = min(chk[y-1][x], chk[y][x-1], chk[y-1][x-1]) +1 if map[y][x] == '1' else 0
        square = square if square >= chk[y][x] else chk[y][x]

print(square*square)