[알고리즘] 백준 - 가장 큰 정사각형

백준 - 가장 큰 정사각형

프로그래머스 - 가장 큰 정사각형 찾기와 아주 유사하며 스타트업 코딩 페스티벌 1차 3번 문제와도 거의 일치한다. 스코페에서는 완전탐색을 했는데도 통과했지만 효율성을 생각해서 dp로 푸는 것이 맞다. 프로그래머스에서 풀고 풀이를 봤는데, 풀이가 완전하게 기억나지 않았다. 역시 답을 본 풀이는 내가 푼게 아니다.

이전 풀이 참조한 풀이

import copy
from itertools import combinations
from collections import deque
import math

n, m = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(n)]

dp = copy.deepcopy(graph)

for i in range(n):
    for j in range(m):
        if dp[i][j] == 0:
            continue
        if i-1 >=0 and j-1 >=0:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

max_val = 0
for i in range(n):
    max_val = max(max_val, max(dp[i]))
print(max_val**2)

풀이를 이번에는 손으로 써서 정리한다. 정사각형의 크기를 오른쪽 밑에 저장한다. dp[i][j] = min(dp[i-1][j] , dp[i][j-1], dp[i-1][j-1]) + 1이다. 물론 원래 배열에서 0이면 그대로 0으로 나둬야한다.