[ baekjoon ] 가장 큰 정사각형 1915번 ( Java )

문제

백준 1915 가장 큰 정사각형 풀이 ( 자바 )

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

풀이

파란색으로 색칠된 항부터 시작하여 해당 위치가 arr[i][j] 라고 한다면(해당 위치 값이 1이어야 함) arr[i-1][j], arr[i-1][j-1], arr[i][j-1] 중(주황색 부분) 에서 가장 작은 값에서 1을 더한 값이 arr[i][j] 값이 되게 한다.

바꾸면 오른쪽 표가 되는데 거기서 가장 큰 값이 가장 큰 정사각형의 한 변의 길이이다.

만약 이런 방법으로 틀렸다고 나온다면 보통은

이 부분을 체크하지 않았기 때문이다. 그렇기 때문에 처음 입력을 받을 때 1값이 하나라도 있다면 answer을 1로 초기화 한다.

 

package baekjoon;

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

public class _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][m];

        int answer = 0;

        for (int i = 0; i < n; i++) {
            String[] tmp = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(tmp[j]);
                if (arr[i][j] == 1) {
                    answer = 1;
                }
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (arr[i][j] == 1) {

                    if (arr[i - 1][j] != 0 && arr[i - 1][j - 1] != 0 && arr[i][j - 1] != 0) {
                        int tmp = Math.min(arr[i - 1][j], arr[i - 1][j - 1]);
                        tmp = Math.min(tmp, arr[i][j - 1]);
                        arr[i][j] = tmp + 1;

                        answer = Math.max(answer, arr[i][j]);
                    }
                }
            }
        }

        System.out.println(answer * answer);

    }
}