Baekjoon 4095 최대 정사각형 JAVA

4095번: 최대 정사각형

문제

1과 0으로 이루어진 NxM크기의 행렬이 주어졌을 때, 1로만 이루어진 가장 큰 정사각형 부분 행렬 찾는 프로그램을 작성하시오. 

입력

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

출력

각 테스트 케이스에 대해서 가장 큰 정사각형의 너비 또는 높이를 출력한다. 만약 그런 정사각형이 없을 때는 0을 출력한다.

풀이

입력받은 행렬에서 좌측 상단부터 우측 하단으로 이동하며 사각형이 만들어 질 수 있는 형태를 구한다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			int max=0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken()), m=Integer.parseInt(st.nextToken());
			if(n==0)
				break;
			int [][] arr = new int[n+1][m+1], dp = new int[n+1][m+1];
			
			for(int i=1;i<=n;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=1;j<=m;j++)
					arr[i][j]=Integer.parseInt(st.nextToken());
			}
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=m;j++)
				{
					if(arr[i][j]==0)
						continue;
					int tmp = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);
                    // 정사각형이 되기 위해서는 좌측, 상단, 좌상단이 존재해야하므로 이 세가지 수 중에서 가장 작은 것을 이용하여 사각형의 크기를 설정한다
					dp[i][j]=tmp+1;
					if(max<dp[i][j])
						max=dp[i][j];
				}
			}
			System.out.println(max);		
		}
	}
}