[백준] 14925번 목장 건설하기 (C++)

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

 

 

이 문제는 N X M 배열이 주어지고 각각의 요소는 0, 1, 2로 주어진다. 0으로된 가장 큰 목장을 정사각형으로 짓는 것이다.

 

이 문제는 https://www.acmicpc.net/problem/1915 문제와 유사하다.

 

가장 큰 정사각형을 만들기 위해서는 하나하나씩 일일히 크기를 만들어가며 탐색할 수 있지만 그렇게 되면 시간복잡도가 O(NM^NM)으로 굉장히 크기 때문에 최적화 할 수 있는 방법을 찾아야 한다.

 

먼저 정사각형이 될 수 있는 조건은 무조건 4변의 길이가 다 같아야 한다는 특징이 있다.

 

따라서 현재 칸에서 0인 경우 왼쪽 칸과 위칸 왼쪽 대각선 칸을 비교하여 정사각형을 만들 수 있는지 확인해야 한다.

 

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

 

이러한 점화식을 세울 수 있는데 이 점화식이 의미하는 것은 현재칸이 0인 경우 정사각형을 만들 수 있는데 왼쪽 칸과 위칸 대각선 왼쪽 칸을 비교하여 가장 작은 숫자를 가져와서 1을 더하는 것이다. 

 

가장 작은 숫자를 가져오는 이유는 정사각형이기 때문에 변의 길이중에서 가장 작은 칸을 가져와 정사각형을 만들어야 한다.

 

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
int graph[1001][1001];
int dp[1001][1001];

void solve() {
    int answer = 0;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if(graph[i][j] == 0) {
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                answer = max(dp[i][j], answer);
            }
        }
    }

    cout << answer;
}

void input() {
    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            cin >> graph[i][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}