[BOJ 1915] 가장 큰 정사각형

문제 링크 : https://www.acmicpc.net/problem/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개의 숫자로 배열이 주어진다.

출력

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

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

이 문제는 $n \times m$ 크기의 2차원 배열에서 ‘1’로만 이루어진 가장 큰 정사각형의 넓이를 찾는 문제이다. $n$과 $m$이 최대 $1\,000$으로 주어지므로, 배열의 전체 칸 수는 최대 $1\,000\,000$개이다. 모든 칸에 대해 정사각형 여부를 전수 조사하면 시간 초과가 발생할 수 있으므로, 다이나믹 프로그래밍을 활용하여 효율적으로 해결한다.

알고리즘의 핵심 논리는 다음과 같다:

• DP 테이블 정의: dp[i][j]를 $(i, j)$ 위치를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변의 길이라고 정의한다.
• 점화식 도출: 현재 칸 grid[i][j]가 ‘1’일 때, 이 칸을 포함하여 정사각형을 만들려면 왼쪽, 위쪽, 그리고 왼쪽 대각선 위쪽 칸들이 모두 정사각형의 일부여야 한다. 따라서 현재 칸의 변의 길이는 세 인접한 DP 값 중 최솟값에 1을 더한 값이 된다.

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

• 초기값 설정: 배열의 첫 번째 행과 첫 번째 열은 스스로가 정사각형의 최대 크기가 되므로, grid의 값에 따라 $0$ 또는 $1$로 초기화한다.
• 결과 도출: 전체 DP 테이블을 채우면서 얻은 변의 길이의 최댓값(result)을 구한다. 문제에서 요구하는 것은 넓이이므로 최종적으로 result * result를 출력한다.

이 방식은 중첩 반복문을 통해 배열을 단 한 번만 순회하므로 시간 복잡도는 $O(nm)$이며, 최대 $1\,000\,000$번의 연산으로 1초의 시간 제한 내에 여유롭게 통과할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 다이나믹 프로그래밍