가장 큰 정사각형 - 1915

[Gold IV] 가장 큰 정사각형 - 1915

문제 링크

분류 📌

다이나믹 프로그래밍(dp)

문제 설명 📌

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

출력 📌

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

풀이 🏆

• 우선, 모든 경우에 대해 살펴보는 완전 탐색은 시간초과가 발생한다
• 예를 들어 n, m이 1000이고 모든 칸이 1로 주어졌을 때 정사각형을 만드는 경우의 수는 1x1 정사각형이 1000x1000개, 2x2 정사각형이 999x999개, 3x3 정사각형이 998x998개 … 1000x1000 이 1x1개다.
• 따라서 총 개수는 1000((1000+1)(2x1000+1))/6 이다.
• 완전 탐색 대신 DP를 이용
• 어떤 가장 큰 정사각형이 있을 때, 이 정사각형 내부는 더 작은 정사각형으로 이루어져 있어서 이 점을 이용하여 DP로 풀수 있다.

구현 🚀

• DP는 우측 하단의 좌표를 삼는 가장 큰 정사각형의 한 변의 길이라고 함
• 우측 하단을 기준으로 왼쪽, 오른쪽, 좌측 상단에 DP값이 모두 있어야 정사각형이 된다
• 만약 왼쪽, 오른쪽, 좌측 상단의 DP값이 제각기 다른 수 라면 가장 작은 값을 선택해야 공통인 변 길이를 가지기 때문에 정사각형을 만들 수 있음

코드 📃

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

board = [list(map(int, input())) for _ in range(n)]
ans = max(board[0])
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-1], board[i-1][j], board[i][j-1]) + 1
    ans = max(ans, max(board[i]))

print(ans**2)