[BOJ] 백준 1915 가장 큰 정사각형 - Python/Java

 

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

1915번: 가장 큰 정사각형

 

이 문제를 직관적으로 생각해보면 아래와 같은 완전탐색에 대한 아이디어를 떠올릴 수 있습니다.

 

"이차원 배열에 존재하는 모든 점에 대해 해당 지점을 오른쪽 아래 모서리라고 생각한 뒤, 정사각형 길이를 1부터 늘려나가보면서 이전 지점들을 탐색하고, 모두 1로 채워져있으면 정사각형 크기를 갱신한다."

 

하지만 이 방식으로 문제를 해결하면 결국 맨 끝의 점에서는 시간복잡도가 O(N^3)에 가까워지는 것을 예상할 수 있습니다.

 

따라서, 이 문제는 위의 정의를 바탕으로 DP를 이용해서 해결할 수 있는데요. 'dp[i][j] = (i, j) 지점에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이'로 정의하게 되면, 전체 최적해는 그 이전의 최적해를 통해 구할 수 있게 됩니다.

 

만약 dp[i][j]를 구한다고 해봅시다. 우선 해당 지점의 값이 0이면 애초에 정사각형을 만들 수 없기 때문에 패스하고, 해당 지점의 값이 1이라면 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 지점의 값을 살펴봐야 합니다. 왜 그럴까요?

 

만약 (i, j) 지점에서 만드는 정사각형이 (i-1, j-1) 지점에서 만드는 정사각형을 포함한다면 dp[i][j] = dp[i-1][j-1] + 1이 되겠죠? 그런데, 문제는 아래 그림처럼 (i-1, j-1) 지점의 값만 봐서는 (i, j) 지점 왼쪽과 위쪽의 값들이 전부 1인지 확인할 수 없습니다. 따라서, 고려해야 하는 지점은 총 세 군데가 되고, 해당 지점들 중 가장 짧은 정사각형의 변의 길이를 가지는 쪽을 참조할 수밖에 없습니다.

 

 

DP 테이블은 현재 값을 갱신하기 위해 이전의 값들이 미리 계산되어 있어야 하므로, 가상의 초기값들을 0으로 세팅합니다. 테두리를 하나 더 생성한다고 이해하면 좋을 것 같습니다. 그리고 i, j에 대한 반복문을 수행하게 되면 그 이전의 값들은 미리 계산이 되어 있을 것입니다.

 

[풀이 - 파이썬]

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
answer = 0
grid = [list(map(int, input().rstrip())) for _ in range(n)]

# dp[i][j] = (i,j)위치에서 자신을 왼쪽 아래 모서리로 하는 정사각형 길이를 저장
dp = [[0] * (m+1) for _ in range(n+1)] # 테두리는 0으로 초기화

for i in range(1, n+1):
    for j in range(1, m+1):
        # 현재 위치가 0이라면 정사각형 만들 수 없음
        if grid[i-1][j-1] == 0: continue
        else:
            dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
            answer = max(answer, dp[i][j])
print(answer ** 2)

 

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_1915 {
    public static int n, m;
    public static char[][] grid;
    public static int[][] dp;
    public static int answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        grid = new char[n][m];
        dp = new int[n+1][m+1]; // 테두리를 0으로 초기화

        for(int i = 0; i < n; i++){
            grid[i] = br.readLine().toCharArray();
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                // 현재 위치가 0이라면 정사각형 만들 수 없음
                if(grid[i-1][j-1] == '0') continue;
                else{
                    // 자신의 왼쪽, 위쪽, 왼쪽 위 대각선에서 만들 수 있는 정사각형 크기의 최소값 참고
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    answer = Math.max(dp[i][j], answer);
                }
            }
        }
        System.out.println(answer * answer);
    }
}