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

문제

접근 방법

가장 큰 정사각형의 크기를 구하는 문제이다.

정사각형은 작은 정사각형으로 이루어져 있음을 생각해 보면 다이나믹 프로그래밍으로 접근할 수 있음을 알 수 있다.

나무와 바위가 없는 곳일 경우 왼쪽, 위, 대각선을 확인하여 가장 작은 값에서 1을 더하는 방식으로 접근하면 된다.
나무, 바위가 존재할 경우 해당 위치는 0의 값을 유지할 것이기에 해당 위치를 요소로 하는 정사각형의 경우 1의 값을 가지게 될 것이다. 그렇기에 최대 정사각형 길이임을 확인할 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
int M, N, ret;
vector<vector<int>> map, dp;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> M >> N;
    map = dp = vector<vector<int>>(M, vector<int>(N));
    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> map[i][j];
        }
    }

    dp[0][0] = ret = (map[0][0] == 0) ? 1 : 0; // 첫 칸에 나무나 바위가 있는가?

    for (int i = 1; i < N; ++i) // 가로 확인
    {
        if (map[0][i] != 0)
        {
            continue;
        }
        dp[0][i] = ret = 1;
    }
    for (int i = 1; i < M; ++i) // 세로 확인
    {
        if (map[i][0] != 0)
        {
            continue;
        }
        dp[i][0] = ret = 1;
    }

    for (int i = 1; i < M; ++i)
    {
        for (int j = 1; j < N; ++j)
        {
            if (map[i][j] != 0) // 만약 나무나 바위가 있다면
            {
                continue;
            }
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; // 위, 왼쪽, 대각선 확인
            ret = max(ret, dp[i][j]);
        }
    }
    cout << ret;
    return 0;
}

풀이

가로 또는 세로가 0인 경우도 값을 갱신해 줘야 한다.
실수로 배열을 착각하여 dp가 아닌 map에 값을 변경해 줬었다.
이러한 실수는 조심하는 것이 좋다.