[SWEA]최대 공백 정사각형 - SWEA4062

문제

• 참고 : SWEA4062

풀이

코드

package ProblemSolution.DP_Detail;

import java.util.*;
import java.io.*;
public class LargestEmptySquare_SWEA4062 {
    static int[][] inArr = new int[1005][1005];
    static int[][] lesArr = new int[1005][1005];

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk;
        int T = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        for(int t = 0 ; t<T; t++) {
            // init
            String inStr = "";
            for(int i=0;i<N+1;i++) {
                Arrays.fill(inArr[i], 0);
                Arrays.fill(lesArr[i], 0);
            }
            // input
            for(int i = 0 ; i<N;i++) {
                stk = new StringTokenizer(br.readLine());
                inStr = stk.nextToken();
                for(int j = 0 ; j<N; j++) {
                    if(inStr.charAt(j)=='1') inArr[i][j] = 1;
                }
            }
            // run
            int result = 0;
            for(int i = 0; i<N;i++) {
                for(int j = 0 ; j<N; j++) {
                    if(inArr[i][j] == 1) lesArr[i][j] = 0;
                    else if(i==0 || j==0) lesArr[i][j] = 1;
                    else {
                        int temp = Math.min(lesArr[i-1][j-1], lesArr[i-1][j]);
                        lesArr[i][j] = Math.min(temp, lesArr[i][j-1]) + 1;
                    }
                    result = Math.max(result, lesArr[i][j]);
                }
            }
            sb.append('#').append(t+1).append(' ').append(result).append('\n');
        }
        // output
        System.out.println(sb);
    }
}