[백준] 1915번 - 가장 큰 정사각형 (Gold 4)

문제 링크

[백준] 1915번 - 가장 큰 정사각형 (Gold 4)

문제 설명

0, 1로 된 크기 n x m인 배열이 있다.
이 배열에서 1로만 이루어진 가장 큰 정사각형의 크기를 구하시오.

정답 코드 및 설명

1로만 이루어진 1 x 1, 2 x 2 정사각형의 위치는 체크하기 쉽다.
p x p 정사각형이 있는 위치를 체크한 배열 $arr_p$가 있다고 가정하자.
정사각형의 위치는 맨 왼쪽, 맨 위쪽의 꼭짓점의 위치로 정의한다.
그러면 $arr_p$에 2 x 2 정사각형이 있는 위치가 처음 배열에서 (p + 1) x (p + 1) 정사각형이 있는 위치이다.

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

public class BOJ1915 {
    int n, m;
    int[][] arr;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = row.charAt(j) - '0';
            }
        }
    }

    boolean is22Square(int i, int j) {
        return arr[i][j] == 1 && arr[i + 1][j] == 1 && arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1;
    }

    // 1이 있는지 체크(처음에 입력을 받을 때 같이 수행해도 된다)
    boolean arrHas1() {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) count++;
            }
        }
        return count != 0;
    }

    int maxSquareSize() {
        int size = 1;
        // 1이 아예 없다면 정사각형의 최대 크기는 0
        boolean arrHasSize = arrHas1();
        if (!arrHasSize) return 0;
        // 1이 있기는 한 경우
        while (true) {
            int count = 0;
            for (int i = 0; i < n - size; i++) {
                for (int j = 0; j < m - size; j++) {
                    if (is22Square(i, j)) { // (size + 1) * (size + 1) 정사각형 체크
                        arr[i][j] = 1;
                        count++;
                    } else arr[i][j] = 0;
                }
            }
            if (count == 0) break; // (size + 1) * (size + 1) 정사각형이 없는 경우
            else size++; // 있는 경우 size를 늘려서 다시 탐색
        }
        return size * size;
    }

    void solution() throws IOException {
        input();
        System.out.println(maxSquareSize());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1915().solution();
    }
}