[BOJ] 가장 큰 정사각형 (1915, G4)

 

문제 풀이 과정

간단한 DP 문제입니다. 순서대로 점을 탐색하며, 현재 위치에서 만들 수 있는 가장 큰 정사각형을 찾습니다.
정사각형은 4개의 꼭지점이 만들고.. 이는 현재 점의 좌측, 위측, 왼쪽 위측에서 정사각형을 만들어주고 있나?로 탐색합니다.

import sys
input = sys.stdin.readline

rows, cols = map(int, input().split())
maps = []
for _ in range(rows):
    cur_row = list(str(input().rstrip()))
    cur_row = [int(x) for x in cur_row]
    maps.append(cur_row)

dp = [[0 for _ in range(cols)] for _ in range(rows)]

max_size = 0
for i in range(rows):
    for j in range(cols):
        if i == 0 or j == 0:
            if maps[i][j] == 1:
                dp[i][j] = 1
                if max_size == 0:
                    max_size = 1
            else:
                dp[i][j] = 0
        else:
            if maps[i][j] == 0:
                dp[i][j] = 0
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
                max_size = max(max_size, dp[i][j])
print(max_size ** 2)