[백준 1915] 가장 큰 정사각형 - Java 문제풀이

오늘의 1일 1골드 문제는 다음 문제이다.

 

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

해설

보통 문제에서 ~의 합을 이용해서 푸는 경우에는 dp를 이용하여 각 지점까지의 누적합을 계산하여 푸는 것이 시간초과가 나지 않는 방법이다.

이 문제와 같은 경우에도 마찬가지이다. 

 

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

 

와 같은 표가 주어졌을 때, (0,0) 부터 각 지점까지의 1의 합을 구한 후 계산하면 된다.

우선 위의 예시에 대한 누적합을 구하면 누적합 표가

 

0	1	1	1
0	2	3	4
1	4	6	7
1	4	7	8

 

와 같이 된다. 

 

어떤 좌표들에서 왼쪽 위 좌표와 오른쪽 아래 좌표만 있다면 사각형을 그릴 수 있다. 이를 이용하면 되는데, 나 같은 경우에는 이중 for문을 돌며 오른쪽 아래 좌표를 (i,j)라고 하고, 왼쪽 위 좌표를 (i-length, j-length)라고 하였다. 여기서 왼쪽위 좌표의 경우 해당 좌표까지 사각형에 포함되지 않는다는 것으로 생각하였다.

그렇다면 그림을 그리면 다음과 같다.

해당 부분은 i=4, j=4, length=2일 때이다. 이 경우 다음과 같이

 

두 파란 부분을 더한 후, 초록 부분을 빼면 주황 부분이 나온다는 것을 이용하면, 전체 (4,4)지점에서 해당 주황부분을 빼면 노란 부분이 나온다는 것을 알 수 있다.

 

따라서 어떤 지점(i, j)에서 한 변이 길이가 length인 사각형의 넓이는

arr[i][j] - arr[i-length][j] - arr[i][j-length] + arr[i-length][j-length]

 

임을 알 수 있다. 그러면 이 넓이가 length*length와 같을 때, length의 최댓값을 구하면 된다 (이 작업은 while문을 이용해주었다)

 

다음은 코드 전문이다.

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

public class BOJ_1915 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());
        int[][] arr = new int[N+1][M+1];
        for(int i=1;i<=N;i++) {
            String str = br.readLine();
            for(int j=1;j<=M;j++) {
                arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1]+ str.charAt(j-1)-'0';
            }
        }
        for(int i=1;i<=N;i++) System.out.println(Arrays.toString(arr[i]));
        int answer = 0;
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=M;j++) {
                if (arr[i][j]==0) continue;
                int length = 1;
                while(true) {
                    if (i-length <0 || j-length <0) break;
                    if (arr[i][j] - arr[i-length][j] - arr[i][j-length] + arr[i-length][j-length] == length * length) {
                        answer = answer > length ? answer : length;
                        length++;
                    }
                    else break;
                }
            }
        }
        System.out.println(answer*answer);
    }
}

 

---

 

역시 DP는 쉬운 듯 어렵다. 아이디어만 떠올리면 쉬운데, 그 아이디어를 떠올리기가 쉽지 않은 것 같다. 다행히 사각형의 넓이를 구하는 방법이 빨리 떠올라서 문제를 푸는 데에 그렇게 긴 시간이 걸리지 않은 것 같다.

이번 문제는 약 30분 정도가 소요되었는데, DP 관련 문제를 많이 연습해서 시간을 단축하기 위해 노력해야 겠다.