[BOJ_1932]_가장 큰 정사각형_python

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

1915번: 가장 큰 정사각형

문제

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개의 숫자로 배열이 주어진다.

출력

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

 

문제해결

dfs로도 고민을 해보았지만 다이나믹 프로그래밍을 이용하여 해결가능한 문제입니다.

단순히 반복문을 이용하여 소스코드를 작성해 작은 문제부터 답을 도출한다고 하여 bottom up(보텀업)방식으로 문제를 해결할 수 있습니다.  board에 해당하는 dp를 따로 생성하여 값을 저장해 나가는 식으로 문제해결을 할 수 있으나 board에 값을 누적해 가는 방식으로 하여 사각형의 넓이를 구하기위해 필요한 한변의 길이값을 저장해 나갔습니다.

 

구조적으로 보았을때 가장 작은 정사각형을 4등분으로 나누고 행렬좌표로 보았을 때 board[i][j](i>0)는 사각형의 오른쪽 아래에 위치합니다. 정사각형은 변의 길이가 하나작은 정사각형4개를 붙여 만든 모양입니다. board[i][j]의 위치에서 정사각형인지 확인을 하려면 board[i][j-1],board[i-1][j],board[i-1][j-1] == True인지 확인을 하면됩니다. 이렇게 1이 들어있는 해당 좌표를 확인후 해당 점화식이 True(정사각형)인지 확인하는 방식으로 점화식을 만들 수 있습니다.

board[i][j] = min(board[i][j-1],board[i-1][j],board[i-1][j-1])+1 해당 좌표에 0이있다면 board[i][j]의 값은 그대로 1일테고 min값이 1이 리턴되면 board[i][j](오른쪽아래)의 값은 2로 초기화되어 변의 길이값을 저장할 수 있게됩니다.

dp문제는 dp인지 아닌지를 판별하는 것과 점화식의 규칙성을 찾는게 중요하다고 다시 한번 깨닫게 되는 문제였습니다.

 

더 효율적이거나 직관적인 풀이가 있다면 편하게 댓글 남겨주시면 감사하겠습니다!

 

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

for i in range(1, n):
    for j in range(1, m):
        if board[i][j] == 1:
            board[i][j] = (min(board[i-1][j], board[i][j-1], board[i-1][j-1])+1)
re_value = 0
for i in range(n):
    re_value = max(max(board[i]),re_value)

print(re_value**2)