[백준] 1915번 : 가장 큰 정사각형 - DP

 

1915번: 가장 큰 정사각형

1915번: 가장 큰 정사각형

너 DP 좀 치냐 ?

이번 문제는 DP 문제입니다.

 

 

문제

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

0100

0111

1110

0010

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

 

 

문제 접근

배열을 순차적으로 돈다고 했을 때

이미 정사각형을 구한 부분도 다시 구하게 된다는 사실은 당연히 알 수 있습니다.

 

때문에 이 부분을 방지할 수 있는 방법이 필요합니다.

 

처음에 저는

한 좌표에서 right, rightDown, down 3가지 방향으로 뻗어 나아가서 정사각형을 구하는 방식을 채택했습니다.

가능은 했으나 구현하기가 만만치 않았습니다.

 

벽에 부딪히거나 숫자가 0이거나 혹은 이미 구한 정사각형의 좌표들의 값을 변경해서 중복을 방지해야 하는데

정확하게 정사각형이라는 것이 확정 되어야 할 수 있는 것으로 세부적으로 구현해야 할 것이 너무 많았습니다.

또한 DP의 꽃인 점화식이 나오지 않았습니다.

 

때문에 점화식으로 풀 수 있도록

즉, 이 문제를 어떻게 세부적으로 나눌 수 있을까 고민했습니다.

 

첫 번째, 1이 존재하는 좌표의 최소 정사각형 크기는 1이다.

 

그렇다면 전에 생각한 것을 다시 꺼내봤습니다.

 

처음 주어진 좌표에서 right, rightDown, down이 1이라면 크기가 4인 정사각형이 됩니다.

하지만 하나라도 1이 아니라면 정사각형이 되지 않습니다.

크기가 4인 정사각형이 되었고 다음에 좌표로 이동 했을 때 그 좌표가 1이면 똑같이 right, rightDown, down을 검색하게 됩니다.

그렇다면 현재 구한 정사각형의 크기가 2이고 다음에 연속해서 1이 온다고 하면 크기가 3인 정사각형을 구하고 있다는 것을 알려주고 싶었습니다.

 

그렇다면 어딘가에 그 정보를 저장해줘야 하고 그 정보를 어떻게 사용해야할지 고민입니다.

 

크기가 9인 정사각형은 크기가 4인 정사각형이 4개가 나오는데

크기가 4인 각 정사각형 오른쪽 하단이 모이면 오른쪽 하단 크기가 4인 정사각형이 나옵니다.

 

그렇다면 왼쪽, 오른쪽, 왼쪽아래 정사각형이 모였을 때

오른쪽 아래 정사각형이 존재한다면 크기가 9인 정사각형이 만들어짐을 알 수 있습니다.

 

그리고 그 크기가 다 4라는 것을 알려주기 위해서도

오른쪽 하단에 기입해주면 한번에 그 정보를 얻을 수 있었습니다.

 

때문에 크기가 1이면 1을 크기가 4면 2를 즉, 가로 혹은 세로의 길이를 적어주고 그 값들이 모였을 때 크기가 9인 정사각형이 되고 오른쪽 하단에 3을 적어줍니다.

 

똑같이 크기가 9인 정사각형이 모이면 크기가 16인 정사각형을 추출할 수 있습니다.

 

 

 

가장 큰 정사각형 구현 코드

코드는 right, rightDown, down으로 바라보지 않고

현 좌표 기준 left, leftUp, up을 바라보고 있습니다.

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

public class Main {
    static int N, M;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dp = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            char[] c = br.readLine().toCharArray();
            for (int j = 1; j <= M; j++) {
                dp[i][j] = c[j - 1] - '0';
            }
        }

        int answer = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (dp[i][j] != 1) continue;
                int left = dp[i][j - 1];
                int leftUp = dp[i - 1][j - 1];
                int up = dp[i - 1][j];

                int min = Math.min(left, Math.min(leftUp, up));
                dp[i][j] = min + 1;
                answer = Math.max(answer, dp[i][j]);
            }
        }
        System.out.println(answer * answer);
    }
}