[알고리즘][Python] 백준(BOJ) 1915 가장 큰 정사각형_파이썬

 

1915 가장 큰 정사각형    www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

 

풀이

<내용>

• 배열을 입력받는다.
• 이중 for문을 돌면서
  • (i, j)가 1이 아니라면 정사각형을 만들 수 없다.
  • 1이라면 (i-1, j), (i, j-1), (i-1, j-1)에서 만들 수 있는 정사각형의 변의 최대 길이 중 최솟값 + 1의 크기로 만들 수 있다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().rstrip())) for _ in range(n)]
for i in range(1, n):
    for j in range(1, m):
        if board[i][j] != 0:
            board[i][j] += min(board[i-1][j-1], board[i-1][j], board[i][j-1])
            
res = 0
for row in board:
    res = max(res, max(row))
print(res**2)