[SWEA] 4062 Largest Empty Square

출처: [SWEA] SW 문제해결 심화 - 동적 계획법

 Input 

1

4

0100

1001

1000

0101

 

 Output 

#1 2

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

『0』과 『1』로 구성된 N×N행렬이 존재합니다.

『0』으로 된 가장 큰 정사각형의 한 변의 길이를 구하시오

- Test Cast 개수 T / 행렬의 크기 N

- 행렬 정보가 공백없이 주어집니다.　

 

자세한 풀이는 [BOJ] 1915 가장 큰 정사각형 참고하면 됩니다.

[BOJ] 백준 1915 가장 큰 정사각형

단, 해당문제는 『0』과 『1』의 의미가 다르므로 입력받을 때 서로 바꿔줍니다.

또한, 정사각형의 크기가 아닌 한 변의 길이를 출력해야 합니다.

 

---

import java.io.IOException;
import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
         
        int T = Integer.parseInt(sc.next());
        for (int tc = 1; tc <= T; tc++) {
             
            int N = Integer.parseInt(sc.next());
            int[][] map = new int[N+1][N+1];
            for(int i=1; i<=N; i++) {
                String str = sc.next();
                for(int j=1; j<=N; j++) {
                    map[i][j] = str.charAt(j-1) - '0';
                    if(map[i][j] == 0) map[i][j] = 1;
                    else map[i][j] = 0;
                }
            }
             
            int[][] DP = new int[N+1][N+1];
            int answer = 0;
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(map[i][j] == 1) {
                        DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1;                
                        answer = Math.max(answer, DP[i][j]);
                    }
                }
            }
             
            System.out.print("#" + tc + " ");
            System.out.println(answer);
        }
    }
     
    private static int min(int A, int B, int C) {
        return Math.min(Math.min(A, B), C);
    }
}