BOJ 1915

2020-10-02

위 문제는 백준 사이트의 알고리즘 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개의 숫자로 배열이 주어진다.

출력

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

소스코드


import java.util.*;
public class Main {
    static int N,M,answer;
    static String str;
    static int[][] array = new int[1001][1001];
    static int[][] dp = new int [1001][1001];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        for(int i=0; i<N; i++){
            str = scanner.next();
            for(int j=0; j<M; j++){
                array[i][j] = str.charAt(j)-'0';
                if(array[i][j]==1){
                    dp[i][j] = 1;
                    answer = 1;
                }
            }
        }
        for(int i=1; i<N; i++){
            for(int j=1; j<M; j++){
                if(array[i-1][j]==1 && array[i-1][j-1]==1 && array[i][j-1]==1){
                    dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]);
                    dp[i][j] = Math.min(dp[i][j],  dp[i][j-1]) + 1;
                }
                answer = Math.max(dp[i][j], answer);
            }
        }
        System.out.println((int)Math.pow(answer, 2));
        scanner.close();
    }
}

이번 문제는 DP로 푸는 문제 였습니다.

문제 내용은 간단해보였는데, 정답률은 낮은 문제였습니다.

처음엔 완전 탐색으로 풀면 되겠다 싶었는데 생각대로하면 뭔가 시간초과가 날 듯 했습니다..

이번 문제의 해결법

현재 제가 확인하고 있는 순번 i, j번째라 하면

  1. 위 = i-1, j

  2. 왼쪽 = i, j-1

  3. 왼쪽 위 = i-1, j-1이 모두 1인지를 확인합니다.

이것을 만족한다면 그 크기까지가 정사각형을 만족하기에 그중 가장 작은 값에 +1을 해줍니다.

이것을 코드로 바꾸면 아래와 같습니다.

d[i][j] = Math.min( d[i-1][j],  d[i-1][j-1],  d[i][j-1]) + 1;

이때 결과값으로 저장되는건 한 변의 길이와 같으므로 결과값은 answer의 제곱과 같습니다.

가장 큰 정사각형