[백준]#14925 목장 건설하기

문제

랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다.

그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다.

땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자.

이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미한다. 랜드씨의 땅에서 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기 L을 출력하시오.

입력

M N
M x N 행렬

• 1 <= M <= 1000
• 1 <= N <= 1000

출력

L

예제 입력 1

6 6
0 0 0 1 0 0
0 0 0 2 1 0
0 0 2 0 0 0
0 1 0 0 0 0
2 0 0 0 0 0
0 0 0 0 0 0

예제 출력 1

3

풀이

이 문제는 DP 알고리즘을 이용해서 풀었으나 최적의 풀이인지는 잘모르겠다. 시간이 꽤 많이 썼기 때문에 좀 더 고민할 필요가 있을 듯 하다.

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

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int M = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);
        int max = 0;
        int[][] dp = new int[M+1][N+1];

        for(int i=1; i<=M; i++) {
            input = br.readLine().split(" ");
            for(int j=1; j<=N; j++) {
                if(Integer.parseInt(input[j-1])==0) {
                    int min = Integer.MAX_VALUE;
                    min = Math.min(Math.min(Math.min(min, dp[i-1][j]), dp[i][j-1]), dp[i-1][j-1]);
                    dp[i][j] = min+1;
                    if(max<dp[i][j]) max = dp[i][j];
                }
            }
        }
        System.out.println(max);
    }
}