[백준/1915] 가장 큰 정사각형 (python)

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

1915번: 가장 큰 정사각형

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:04:54

 

---

 

문제 설명

 

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

 

 

입력 및 출력

 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

 

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

 

입력 예시

4 4
0100
0111
1110
0010

 

출력 예시

4

 

 

---

 

풀이

 

아래 풀이를 참조해보자!

2023.02.21 - [알고리즘 문제/백준] - [백준/1460] 진욱이의 농장 (Python3)

[백준/1460] 진욱이의 농장 (Python3)

 

위 문제도 핵심 풀이를 공유한다!(최대 넓이의 정사각형 찾기 문제는 저런 형식을 띈다고 보는 게 맞겠다!)

 

 

풀이 코드

import sys
input = sys.stdin.readline

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

for i in range(1, n) :
  for j in range(1, m) :
    if square_list[i][j] == 1 :
      square_list[i][j] += min(square_list[i][j-1], square_list[i-1][j], square_list[i-1][j-1])

print(max(map(max, square_list)) ** 2)

풀이 완료~