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

1915번: 가장 큰 정사각형

해당문제는 다이나믹프로그래밍으로 문제를 해결하였습니다.

from pprint import pprint
n, m = map(int, input().split())
move = [(-1,-1), (-1,0), (0,-1)]
cost = [-1 for _ in range(3)]
graph = [[] for _ in range(n)]
for i in range(n):
    char = list(str(input()))
    for num in char:
        graph[i].append(int(num))
        

maxresult = 0
for i in range(n):
    for j in range(m):
        
        for t in range(len(cost)): # 초기값 Init
            cost[t] = -1
        
        for k in range(len(move)):
            dy = i + move[k][0]
            dx = j + move[k][1] 
            if n > dy >= 0 and m > dx >= 0 and graph[dy][dx]:
                cost[k] = graph[dy][dx] + 1
                
        comp = min(cost)
        
        if graph[i][j]:
            graph[i][j] = max(comp, graph[i][j])
            maxresult = max(maxresult, graph[i][j])

print(maxresult*maxresult)

점화식은 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) +1 입니다.

이전에 있던 정사각형이 이미 1x1, 2x2 … 인경우를 판단하여 정사각형의 최대 크기를 구합니다.