알고리즘/DP
[백준 1915] 가장 큰 정사각형 (파이썬 풀이)
파프리카.
2023. 4. 13. 17:11
dp로 푸는 문제. 바깥부터 차례대로 살펴보면 된다.
위와 같이 초록색->노란색->파란색 순으로 경우의 수를 확인하면서 될 수 있는 정사각형의 최대 넓이를 구하면 된다. 자신이 위치하는 칸의 [왼쪽, 왼쪽 위, 위]만 살펴보면 된다.
내 위치가 [i][j]칸이고 칸에 있는 숫자가 1이라면 [i-1][j] 칸, [i-1][j-1] 칸, [i][j-1] 칸 중 가장 최소값을 기준으로 +1을 하면 그게 해당 칸이 오른쪽 아래 꼭짓점일 때 될 수 있는 최대 크기의 정사각형의 변의 길이가 된다.
이 원리를 코드로 표현하면 다음과 같다.
d[i][j] = min(d[i-1][j-1], d[i-1][j], d[i][j-1])+1
아래는 문제의 예제를 입력했을 때와 생성되는 dp 리스트다.
제출코드
n,m = map(int,input().split())
arr = list(input() for _ in range(n))
d = [[0]*m for _ in range(n)]
ans = 0
for i in range(n):
for j in range(m):
if i==0 or j==0:
d[i][j] = int(arr[i][j])
elif arr[i][j]=="0":
d[i][j] = 0
else:
d[i][j] = min(d[i-1][j-1], d[i-1][j], d[i][j-1])+1
ans = max(d[i][j], ans)
print(ans**2)