[BOJ] 1915 - 가장 큰 정사각형

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

난이도: 골드 5

사용언어: JAVA

 

풀이

언뜻 보기에는 bfs로 풀 수 있을 것 같은 문제이지만, 특히 JAVA를 이용해 bfs로 구현을 하면 메모리 초과, 또는 시간 초과가 뜰 확률이 굉장히 높습니다. 이 문제는 bfs 대신 다이나믹 프로그래밍을 이용해 해결할 수 있습니다.

 

우선 arr라는 배열에 입력으로부터 행렬을 받아 넣습니다. 그리고 arr[i][j]를 오른쪽 아래 꼭짓점으로 하는 정사각형의 한 변의 길이를 dp라는 이차원 배열에 저장합니다.

 

arr[i][j]를 우측 하단 꼭짓점으로 하는 정사각형의 한 변의 길이는 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 셋 중에 가장 작은 값에 1을 더한 값과 같습니다. 1을 더한 것은 자기 자신이 더해지기 때문이고, 이미 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]에 어떤 값이 들어가 있다는 말은 이미 해당 값만큼의 정사각형 크기가 확보되어 있다는 뜻이기 때문입니다.

 

 

문제에서의 예시인 위의 값으로부터 구한 dp 배열은 다음과 같습니다.

 

 

참고로 계산의 편의를 위해 arr와 dp 배열 모두 네 가장자리를 0으로 둘러싸주었습니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int n, m;
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        int i, j;
        int max = 0;
        char[][] arr = new char[n + 2][m + 2];
        int[][] dp = new int[n + 2][m + 2];
        for (i = 1; i <= n; i++) {
            s = br.readLine();
            for (j = 1; j <= m; j++) {
                arr[i][j] = s.charAt(j - 1);
            }
        }
 
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                if (arr[i][j] == '1') {
                    dp[i][j] = 1; // 우선 자기 자신을 포함하기 때문에 정사각형의 한 변의 최소크기는 1
                    if (arr[i - 1][j] == '1' && arr[i][j - 1] == '1' && arr[i - 1][j - 1] == '1') { // 왼쪽, 위쪽, 대각선 위쪽이 0이면 i,j를 우측 하단의 꼭짓점으로 하는 정사각형의 한 변의 최대 길이는 1이 될 수 밖에 없음
                        dp[i][j] += Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
                    }
                    max = Math.max(max, dp[i][j]); // 지금까지 정사각형 중에 가장 크다면 max에 저장
                }
            }
        }
 
        bw.write(String.valueOf(max * max)); // 문제가 정사각형의 넓이를 구하는 것이고, dp에 저장한 값들은 한 변의 길이이기 때문에
        bw.flush();
    }
}