[SWEA] 4062:Largest Empty Square(Java 자바)

0으로 입력된 것은 1로, 1로 입력된 것은 0으로 바꿔 map 배열에 넣는다.

dp[0][i] 와 dp[i][0] 에는 모두 자기 자리 값을 넣고 시작

대각선 위, 위, 왼쪽 비교 후 가장 최소값에 +1을 해주면 현재 좌표에서 만들 수 있는 제일 큰 정사각형 너비가 된다.

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

class Solution {
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());

		for (int test_case = 1; test_case <= T; test_case++) {
			int n = Integer.parseInt(br.readLine());
			char[][] map = new char[n][n];
			for(int i=0;i<n;i++) {
				map[i] = br.readLine().toCharArray();
				for(int j=0;j<n;j++) {
					map[i][j] = map[i][j]=='0' ? '1':'0';
				}
			}
			int[][] dp = new int[n][n];
			for(int i=0;i<n;i++) {
				dp[0][i] = map[0][i]-'0';
				dp[i][0] = map[i][0]-'0';
			}
			
			int res = 0;
			for(int i=1;i<n;i++) {
				for(int j=1;j<n;j++) {
					if(map[i][j]=='0') {
						dp[i][j] = 0;
						continue;
					}
					dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1]))+1;
					res = dp[i][j] > res ? dp[i][j]	: res;
				}
			}
			sb.append("#").append(test_case).append(" ").append(res).append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
	}
}