백준 1915[자바] java 가장 큰 정사각형

문제 링크: https://www.acmicpc.net/problem/1915

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

▶출력

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

▶해설

조건을 살펴보겠습니다.

1. 1로 된 가장 큰 정사각형

 

간단한 조건이지만 DP를 사용해야 하기에 쉽지는 않습니다.

 

가장 정사각형을 구하기 위한 방법은 1인 점을 기준으로 12시, 9시, 11시 방향 중에 가장 작은 값+1을 해줍니다. 그 이유는 현재 점을 가장 우측 하단에 있다고 가정하고 접근합니다. 그렇기에 자신의 12시, 9시, 11시 방향 중에 가장 작은 값+1을 넣어주면 됩니다. 

 

예를 보겠습니다. (좌측 상당 1,1 우측 하단 2,2)

2 2

1 0

1 1

(1,1) -> (0,1)=0, (1,0)=0, (0,0)=0 가장 작은 값 =0 +1 ---> 1

(1,2) -> (1,1)=1, (0,2)=0, (0,1) =0 가장 작은 값 =0 +1 ---> 1

(2,1) -> (1,1)= 1, (1,0)= 0, (2,0) =0 가장 작은 값 =0 +1 ---> 1

(2,2) -> (2,1) =1, (1,1)= 1, (1,2) =0 가장 작은 값 =0 +1 ---> 1

 

그렇다면 다른 예시를 보겠습니다. 

2 2

1 1

1 1

(1,1) -> (0,1)=0, (1,0)=0, (0,0)=0 가장 작은 값 =0 +1 ---> 1

(1,2) -> (1,1)=1, (0,2)=0, (0,1) =0 가장 작은 값 =0 +1 --->1

(2,1) -> (1,1)= 1, (1,0)= 0, (2,0) =0 가장 작은 값 =0 +1 --->1

(2,2) -> (2,1) =1, (1,1)= 1, (1,2) =1 가장 작은 값 =1 +1 ---> 2

 

따라서 아래와 같이 arr[i-1][j-1]==1 일때 점화식을 도출 할 수 있습니다. 

if(arr[i-1][j-1]==1){
    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
    result = Math.max(result,dp[i][j]);
}

n==1 혹은 m==1 일 때 조건문을 통해서 ArrayIndexBoundException을 피해야 합니다.

if(m==1){
    for(int i=0; i<n; i++){
        if(arr[i][0]==1){
            System.out.println(1);
            return;
        }
    }
    System.out.println(0);
    return;
}

if(n==1){
    for(int i=0; i<m; i++){
        if(arr[0][i]==1){
            System.out.println(1);
            return;
        }
    }
    System.out.println(0);
    return;
}

 

전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);


        int [][] arr = new int[n][m];
        int [][] dp = new int[n+1][m+1];

        for(int i=0; i<n; i++){
            String s1 = br.readLine();
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(String.valueOf(s1.charAt(j)));
            }
        }

        if(m==1){
            for(int i=0; i<n; i++){
                if(arr[i][0]==1){
                    System.out.println(1);
                    return;
                }
            }
            System.out.println(0);
            return;
        }

        if(n==1){
            for(int i=0; i<m; i++){
                if(arr[0][i]==1){
                    System.out.println(1);
                    return;
                }
            }
            System.out.println(0);
            return;
        }

        for(int i=1; i<=m; i++){
            dp[1][i]=arr[0][i-1];
        }
        int result=0;

        for(int i=2; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(arr[i-1][j-1]==1){
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                    result = Math.max(result,dp[i][j]);
                }
            }
        }
        System.out.println(result*result);
    }
}