[Python] [BOJ] 가장 큰 정사각형(1915)

💡 문제 해결

1. 정사각형 배열의 크기와 같은 dp리스트를 생성
2. 정사각형 배열을 순차적으로 순회하며 값이 존재하는 경우에 해당 좌표의 상, 좌, 좌측상단의 dp리스트 값 중 최소값을 해당 좌표 dp리스트에 저장
3. 만약 해당 dp리스트의 좌표 값이 answer보다 크면 answer값 갱신
4. answer에 저장된 값이 가장 긴 정사각형의 한 변 길이이므로 제곱하여 정답 출력

📌 dp없이 풀려고 도전했다가 시간초과만 났던 문제
📌 상, 좌, 좌측상단의 값을 탐색할 때 리스트의 범위를 벗어날 수 있지만 벗어나는 좌표의 dp리스트 값은 아직 탐색을 하기 전 값이므로 상관이 없음

🧾 문제 설명

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

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

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

문제보기

🖨 입출력

📝 풀이

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, input().strip('\n'))) for _ in range(N)]

dp = [[0] * M for _ in range(N)]
answer = 0
for i in range(N):
    for j in range(M):
        if arr[i][j]:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
            if dp[i][j] > answer:
                answer = dp[i][j]

print(answer ** 2)

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/1915