프로그래밍/백준
백준 1915: 가장 큰 정사각형 해설- python
Platypus
2022. 2. 19. 11:09
728x90
반응형
✏️ 문제
https://www.acmicpc.net/problem/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)
728x90
반응형