[BOJ 백준] 가장 큰 정사각형 (1915) Java

링크 : https://www.acmicpc.net/problem/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개의 숫자로 배열이 주어진다.

 

출력 : 

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

 

예제 입력 : 

4 4
0100
0111
1110
0010

 

예제 출력 : 

4

 

접근법 : 

1) 어떻게 풀 것인가?

N이 1,000이고, N^2으로 모든 경우의 수를 체크한다면 시간이 안정적으로 보여진다.

 

즉, 2중 for문으로 가로, 세로를 보면서

해당 정점에서 가능한 최대 정사각형의 크기를 기록을 해야 안정적으로 

시간복잡도를 통과할 것으로 판단했다.

 

그래서 입력받는 N*M은 map[ i ][ j ]로 남겨두고

dp[ i ][ j ]을 선언해서 ( i, j ) 가 가장 우측 하단에 위치하는 정사각형의 한 변의 크기라고 하기로 했다.

 

예를 들면 예제에 표현된 그림에서는 아래와 같이 표현할 수 있다.

DP(2,2) = 1   - (2, 2) 가 우측 하단인 가장 큰 정사각형은 1

DP(3,3) = 2   - (3, 3) 이 우측 하단인 가장 큰 정사각형은 2

 

이를 위해서 정사각형의 성질에 대해 생각해봤는데,

아래 3가지 조건으로 정리할 수 있었다. dp[ i ] [ j ] 의 크기가 측정이 되려면

 

① map[ i ] [ j ] 는 반드시 1이어야한다.

② 바로 직전의 값 (dp[y-1][x-1] ↖), (dp[y][x-1] ←), (dp[y-1][x] ↑) 중 하나라도 0이면 정사각형의 크기는 최대 1이다.

③ (dp[y-1][x-1] ↖), (dp[y][x-1] ←), (dp[y-1][x] ↑) 의 값 중 가장 작은 값 + 1 이 최종 정사각형 한 변의 길이가 된다.

 

3가지 조건을 getSquareSize함수로 이렇게 구현했다.

    // 가능한 최대 정사각형 변의 길이를 return하는 함수
    static int getSquareSize(int y, int x) {
        // 체크대상 : 1. 좌측 위 대각선 (↖), 2. 좌측 (←),  3. 위(↑)  
    	int check1 = dp[y - 1][x - 1]; 
    	int check2 = dp[y][x - 1]; 
    	int check3 = dp[y - 1][x]; 

    	// 1. 하나라도 0이면 크기 1짜리 정사각형
    	if (check1 == 0 || check2 == 0 || check3 == 0) return 1;
    	
    	// 2. 3개 중에 정사각형이 존재하면 그 최솟값보다 1 큰 정사각형 
    	return Math.min(Math.min(check1, check2), check3) + 1;
    }

전체 코드는 아래 참고.

 

2) 시간복잡도

O(N^2) - N은 1,024로 양호함

(Java 기준 -  388ms)

 

3) 공간복잡도

2차원 배열로 N이 크지 않으므로(1024^2) 특별히 고려하지 않음.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

DP적 사고방식. 부분의 정답을 모아 전체의 정답을 만들기 - 2차원 버전

 

Java 코드 : 

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

// 1915 가장 큰 정사각형
public class Main {

    static int N, M, ans;
    static int[][] map, dp;

    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());

        map = new int[N+1][M+1];
        dp = new int[N+1][M+1];
        String input;

        // 1. 입력
        for (int i = 1; i <= N; i++) {
            input = br.readLine();
            for (int j = 1; j <= M; j++) {
                dp[i][j] = map[i][j] = input.charAt(j - 1)-'0';
            }
        }
        
        // 2. N * M 탐색하면서 가능한 최대 정사각형 확인
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 1) {
                    dp[i][j] = getSquareSize(i, j);
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }

        // 3. 넓이 출력 (가능한 최대 변의 크기 제곱)
        System.out.println(ans*ans);
        br.close();
    }

    // 가능한 최대 정사각형 변의 길이를 return하는 함수
    static int getSquareSize(int y, int x) {
        // 체크대상 : 1. 좌측 위 대각선 (↖), 2. 좌측 (←),  3. 위(↑)  
    	int check1 = dp[y - 1][x - 1]; 
    	int check2 = dp[y][x - 1]; 
    	int check3 = dp[y - 1][x]; 

    	// 1. 하나라도 0이면 크기 1짜리 정사각형
    	if (check1 == 0 || check2 == 0 || check3 == 0) return 1;
    	
    	// 2. 3개 중에 정사각형이 존재하면 그 최솟값보다 1 큰 정사각형 
    	return Math.min(Math.min(check1, check2), check3) + 1;
    }

}