알고리즘 공부/문제 풀이

[JAVA] 백준 4095 최대 정사각형

valid_ming 2021. 10. 8. 15:21

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

 

4095번: 최대 정사각형

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두

www.acmicpc.net

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        while(true){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            if(N==0 && M==0) break;

            int[][] dp = new int[N+1][M+1];

            int max = 0;

            for(int i=1;i<=N;i++){
                st = new StringTokenizer(br.readLine());
                for(int j=1;j<=M;j++){
                    dp[i][j] = Integer.parseInt(st.nextToken());
                    if(dp[i][j]==1) dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));

                    if(max < dp[i][j]) max = dp[i][j];
                }
            }
            sb.append(max).append('\n');
        }


        System.out.println(sb);

    }
}