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

14925번 목장 건설하기

문제

---

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

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

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

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

입력

---

M N

M x N 행렬

1 <= M <= 100

1 <= N <= 1000

출력

---

L

---

풀이)

처음에 for문을 이용해서 풀었다가 시간초과가 난 문제이다.

예외처리를 많이 해주면 괜찮을 줄 알았는데 아니였다.

dp를 이용해서 풀어야하는 문제이다

점화식

dp[i][j] = i행 j열 칸까지 봤을 때 나올 수 있는 정사각형 길이 최대값

각 칸을 살펴볼 때, 이 칸이 정사각형을 이루는 오른쪽 아래칸이라고 생각한다.

따라서 나무나 돌이 있는 칸은 넘기고, 들판이 있는 칸을 계산할 때 위쪽, 왼쪽, 왼쪽 위 대각선 중

나올 수 있는 정사각형 길이의 최소값을 찾은 뒤 그 길이에 +1을 해주면 된다.

(그 길이보다 1 정도 긴 정사각형이 만들어질 수 있다는 뜻)

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

나올 수 있는 가장 큰 정사각형 길이는 dp[][]배열 중 가장 큰 값

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int M, N;
int map[1001][1001];
int dp[1001][1001];
 
int main() {
    scanf("%d %d", &M, &N);
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    int len = 0;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j] > 0) continue;
            //위, 왼쪽, 왼쪽위 대각선
            dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            len = max(len, dp[i][j]);
        }
    }
    printf("%d", len);
    return 0;
}