[JAVA]백준 1915번: 가장 큰 정사각형

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

1. 문제 설명

 

0과 1로 된 n*m 배열이 있을 때 1로만 구성되어있는 가장 큰 정사각형의 크기를 구하는 문제이다.

 

 

현재 위치를 (X, Y)라고 할 때 현재 위치를 포함하고 만들 수 있는 가장 큰 정사각형의 길이를 cache 배열에 저장한다고 하자.

 

cache [X][Y] 값은 cache [X-1][Y-1], cache [X-1][Y], cache [X][Y-1]의 최솟값의 1을 더한 값이다.

 

 

cache [][] 값은 현재 위치에서 cache [][] 값만큼의 길이를 가진 정사각형이 존재한다는 것이기에 인접한 3개의 cache [][] 값으로 사각형의 길이를 구할 수 있는 것이다. 우리는 사각형이 아닌 정사각형을 구하는 것이기에 가로, 세로 길이가 동일해야 하고 따라서 최솟값에 1을 더한 값을 사용하는 것이다.

 

 

 

	Y-1	Y
X-1	cache[X-1][Y-1]	cache[X-1][Y]
X	cache[X][Y-1]	?

2. 코드

 

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    public static int n,m;


    public static int[][] cache=new int[1002][1002];

    public static void main(String[] args) throws IOException {


        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st=new StringTokenizer(br.readLine()," ");

        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());

        int max=0;

        for (int x = 1; x <= n; x++) {
            String temp = br.readLine();

            for (int y = 1; y <= m; y ++) {
                cache[x][y] = temp.charAt(y-1)-'0';
            }
        }

        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                if (cache[x][y] == 1) {
                    cache[x][y] = Math.min(Math.min(cache[x - 1][y - 1], cache[x - 1][y]), cache[x][y - 1]) + 1;

                    if (cache[x][y] > max) {
                        max = cache[x][y];
                    }
                }
            }
        }

        bw.write(String.valueOf(max*max));
        bw.flush();

        bw.close();
        br.close();



    }


}