[DP(Dynamic Programming)] 백준-1915 가장 큰 정사각형 골드4(Python)

백준-1915 : 가장 큰 정사각형

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

풀의

• 1 되어있을 경우 좌, 우, 좌상 값중 가장 작은 값에 1을 더한 값으로 메트릭스 수정한다.
• 갱신 후 결과값보다 크면 결과 값을 갱신한다.

놓쳤던 부분

• 1행 1열 부터 확인하여 0행과, 0열에 1의 값이 있고 그외에 값이 0일때의 케이스를 놓쳤었음 

 

코드 (Python)

import sys

def input():
    return sys.stdin.readline().rstrip()


n, m = map(int, input().split())

matrix = [list(map(int, input().rstrip())) for _ in range(n)]

result = 0

for i in range(n):
    for j in range(m):
        tmp = matrix[i][j]

        if (tmp == 1 and i != 0 and j != 0):
            tmp = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1])+1
            matrix[i][j] = tmp

        result = max(tmp, result)


print(result*result)