[BOJ-1915] 가장 큰 정사각형

 

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

1915번: 가장 큰 정사각형

---

[풀이]

 

프로그래머스 가장큰 정사각형 풀이를 참고하면 됩니다.

2020/04/20 - [알고리즘/Programmers] - [프로그래머스] 가장 큰 정사각형

[프로그래머스] 가장 큰 정사각형

---

[코드]

import sys
from copy import deepcopy
input=sys.stdin.readline

# n: 행, m:열
n,m = map(int, input().strip().split())
A=[ [*map(lambda x: 0 if x=='0' else 1 ,input().strip())] for _ in range(n)]
DP=deepcopy(A)

max_len=max(A[0])
for row in range(1,n):
    for col in range(1,m):
        if A[row][col]==1:
            # (row-1,col-1), (row-1, col), (row, col-1) 이 모두 1인지 확인
            if (A[row-1][col-1]==1) and (A[row][col-1]==1) and (A[row-1][col]==1):
                #길이를 구한다.
                DP[row][col]=min(DP[row-1][col-1], DP[row-1][col], DP[row][col-1])+1
                
                # 가장큰 정사각형의 길이를 구한다.
                max_len=max(max_len, DP[row][col])

print(max_len**2)