[2017 홍익대학교 프로그래밍 경진대회] 14925번 목장 건설하기

문제

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

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

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

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

입력

M N M x N 행렬

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

출력

L

 

큰 정사각형을 빈 정사각형으로 만드는 경우는  i-1xj-1 , i-1xj, ixj-1 이 3가지 영역중에 작은 영억 크기로 부터 +1 더하는 경우다.

그 이유는 저 내부에 가장 작은 부분이란건 정사각형을 만들지 못한 부분을 말하는 것이고한 영역이라도 저 전체 영역을 정사각형을 못만들게하는 ( 장애물이 있는 ) 요소가 있다면

저 전체 큰 정사각형이 정사각형이 될 수 없기 때문에 가장 작은것으로부터 1을 더해준다.

그리고 0 행 이거나 0 열에서 값이 0 인 것에 대해 dp에 직접 1을 저장해놓고 (1,1)부터 시작하면 96퍼에서 자꾸 오답이 발생.

따라서 그냥 1부터 M,N 까지 입력 받고, dp처리 바로 하면 통과한다.

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
int M, N;
int arr[1001][1001];
int dp[1001][1001];



int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	cin >> M >> N;
	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> arr[i][j];
		}
	}
	
	int res = 0;
	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (!arr[i][j])
			{
				dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
				res = max(dp[i][j], res);
			}
		}
	}

	cout << res;

	return 0;
}