백준 1915번 : 가장 큰 정사각형 풀이 (Java) - DP

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

Solution

1. N*M 2차원 배열 dp 를 만들고, 안에 들어가는 값은

dp[a][b] = (a,b) 를 오른쪽 아래로 하는 정사각형 중, 최대 정사각형의 변의 길이 이다.

 

2. 오른쪽 아래를 기점으로 삼는다는 말은,

dp[a-1][b] ( 오른쪽 위 )

dp[a-1][b-1] ( 왼쪽 위 )

dp[a][b-1] (왼쪽 아래)

 

가 모두 1보다 커야 한다.  예제로 한번 보자. 만약에 입력이

4 4

0111

0111

0111

0111

 

이라면, dp 배열은

0 1 1 1 
0 1 2 2 
0 1 2 3 
0 1 2 3 

가 된다. 

천천히 보자. 우선 당연히 (1,1)부터 봐야한다. ( 왼쪽 위까지 봐야 하니까 )

 

• (1,1) 에서는 (0,0), (0,1), (1,0) 을 볼텐데, (0,0) 과 (1,0) 이 0, 즉 정사각형의 선분이 될 수 없으므로 그냥 자신의 값인 1만 유지한다.
• (1,2) 에서라면 ? (0,1), (0,2), (1,1) 을 보는데, 이 3개의 값이 전부 0보다 크다. 즉, 최소 한개의 선분은 가지고 있다는 뜻이 될 것이다. 그럼 일단 직관적으로 봤을 때 선분의 길이가 2인 정사각형을 만들 수 있으므로 넘어가자.

위 예제에서, 우리는 당연히 길이가 3인 정사각형이 최대인 걸 한 눈에 알 수 있다. 근데 문제는, 오른쪽에 세로 길이가 4인 직사각형 형태가 있다는 것인데, 어떻게 3과 4 중에 올바른 값을 골라낼 수 있을까?

 

이 문제가 생길 수 있는, 맨 오른쪽 아래의 (3,3)을 보자.

(2,2) 는 2, (2,3) 은 3, (3,2) 는 2 이다. 즉, (2,2) 까지는 길이가 2인 정사각형을 무조건 만들 수 있다는 것이 보장되고, (2,3)까지는 길이가 3인 정사각형을 무조건 만들 수 있다. (3,2)도 마찬가지로 2인 정사각형을 만들 수 있다.

 

 

여기서 우리가 알 수 있는 것은, 

• arr[i][j] 가 1 이고, (정사각형의 한 꼭지점이 될 수 있고 )
• dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 이 세 곳의 값 중에 최소값+1 의 선분의 길이가 최대 정사각형이라는 것이다.

이 예시에서, (2,2), (2,3), (3,2) 가 모두 3이면, (3,3) 이 1일 때, 길이가 4인 정사각형이 보장된다. 이것만 이해하면 금방 풀 수 있다.

 

Source Code

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N,M, max;
    private static int[][] arr, dp;
    private static void input() throws IOException {
        StringTokenizer nm = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nm.nextToken());
        M = Integer.parseInt(nm.nextToken());
        arr = new int[N][M];
        dp = new int[N][M];
        for(int i = 0 ; i < N; i++) {
            char[] line = bufferedReader.readLine().toCharArray();
            for(int j = 0 ; j < M; j++) {
                arr[i][j] = Character.getNumericValue(line[j]);
                dp[i][j] = arr[i][j];
                if(i >= 1 && j >= 1) {
                    if(dp[i-1][j] > 0 && dp[i-1][j-1] > 0 && dp[i][j-1] > 0 && dp[i][j] > 0) {
                        int min = Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1]));
                        dp[i][j] = min + 1;
                    }
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        for(int i = 0 ; i < N; i++) {
            for(int j = 0 ; j < M; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void solve() throws IOException {
        System.out.println(max * max);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}