백준 1915: 가장 큰 정사각형 해설- python

✏️ 문제

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

1915번: 가장 큰 정사각형

 

✏️ 풀이

시작점에서 대각선(n,m)방향으로 뻗어나가면서 사각형이 만들어지는지를 확인한다.

[i][j]를 기준으로 [i-1][j], [i][j-1], [i-1][j-1]이 모두 0이 아니라면 최소사각형(2x2)가 만들어졌다는 뜻이다.

아래 코드대로 인풋 매트릭스에 값을 더해가다 보면,

이런식으로 매트릭스가 채워질거다. 가장 큰 값이 정사각형의 한변의 길이가 되고 크기는 그 길이의 제곱이된다.

 

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

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

print(len*len)