[백준] 14925번 : 목장 건설하기(JAVA)

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

14925번: 목장 건설하기

풀이

1이나 2가 아닌 0이 있을 때 농장을 지을 수 있습니다.

정사각형을 지을 수 있으면 그자리에 +1해서 사이즈를 추가해줍니다(dp)

-1,0부분, 0,-1부분, -1,-1부분 중 가장 작은 수를 구한후 +1을 시켜 가장 큰 정사각형을 구할 수 있습니다.

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int m = Integer.parseInt(st.nextToken()), n = Integer.parseInt(st.nextToken());
		int[][] board = new int[m][n];
		
		int[][] dp = new int[m + 1][n + 1];
        
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int answer = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(board[i-1][j-1] == 0){
                    dp[i][j] = Math.min(Math.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(answer);
	}
}