[백준1915번] 가장 큰 정사각형 / Python3

문제

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

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

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

입력

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

출력

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

예제 입력 1

4 4
0100
0111
1110
0010

예제 출력 1

4

나의 풀이

이 문제는 다이나믹 프로그래밍 기법을 사용해야 되는 문제로 dp배열을 만들어 풀어야한다. 따라서 dp에는 가로,세로로 최대로 연속되는 변의 길이가 저장이 된다. 주의할 점은 정사각형이 되어야하므로 위와 왼쪽만을 생각하면 안된다는 것이다. 왼쪽 대각선 즉, [i-1][j-1]도 확인을 해주어야한다. 따라서 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 의 세 가지 중 가장 작은 값에 1을 더하면서 저장해나가면 된다. 따라서 점화식은 다음과 같다.

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

주의할 점은 dp배열이 [n+1][m+1] 의 크기로 초기값은 모두 0으로 해주어야한다는 것이다. 이렇게 하지 않으면 0번째 행과 0번째 열을 따로 구해놓아야하기 때문이다. 이 문제는 코드가 간단하므로 코드로 이해를 하고 직접 그림을 그려서 이해하면 금방 이해가 갈 것이다.

코드

# 1915번 가장 큰 정사각형
import sys

# main
n, m = map(int, input().split())

board = []
for _ in range(n):
    board.append(sys.stdin.readline())

# 최대 한 변의 길이를 저장하는 배열
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
maxSide = 0
for y in range(n):
    for x in range(m):
        if board[y][x] == '1':
            # 대각선 위, 위, 왼쪽 중 최솟값에 + 1 저장.
            dp[y+1][x+1] = min(dp[y][x], min(dp[y+1][x], dp[y][x+1])) + 1
            maxSide = max(maxSide, dp[y+1][x+1])

print(maxSide ** 2)