[C/C++] BOJ 14925 :: 목장 건설하기

BOJ 14925 :: 목장 건설하기

문제 링크 : https://www.acmicpc.net/problem/14925

나는 왜 BFS 로 하면 풀 수 있을 것이라고 계속 생각했을까 ㅠㅠ?

1000*1000에 (V+E)만큼 탐색해야 하는 것을 알고 있었지만.. 예외 처리를 많이 해주면 되는 건줄 알고 bfs에서 빠져나오지 못해 계속 시간초과가 나왔다 ㅠ

하다하다 안되어서 결국 이 문제를 푸는 알고리즘을 찾아보았는데 다이나믹 프로그래밍으로 푸는 것이었다.!!!!!!

배열을 처음부터 끝까지 한 번 돌려야 한다는 것을!!! 왜 생각을 못했을까!!!!!!!! 알고나니 빨리 풀렸다.. 흑

나의 풀이

1. 시작 행과 시작 열의 땅에 목장을 세울 수 있다면 1을 저장, 세울 수 없다면 0을 저장한다.

2. 현재 땅이 목장을 건설할 수 있는 땅일 때,

1) ↖, ←, ↑ 방향의 땅이 모두 목장을 건설할 수 있는 땅이었다면, 세 위치의 목장의 한 변의 길이 중 가장 작은 값 + 1을 저장한다.

2) 그렇지 않다면 1을 저장한다.

3. 현재 땅이 목장을 건설할 수 없는 땅일 때,

0을 저장한다.

4. 저장된 배열에서 가장 큰 값을 출력한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_14925/BOJ_14925.cpp

// 백준알고리즘 14925번 :: 목장 건설하기
#include<iostream>
#define max(a,b) a > b ? a : b
using namespace std;
 
int M, N, ans;
int land[1002][1002];
int dp[1002][1002];
 
int minfunc(int a, int b, int c)
{
    if (a < b)
    {
        if (a < c) return a;
        else return c;
    }
    else
    {
        if (b < c) return b;
        else return c;
    }
}
int main(void)
{
    cin >> M >> N;
 
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> land[i][j];
 
            if (i == 1 || j == 1)
            {
                if(land[i][j]) dp[i][j] = 0;
                else dp[i][j] = 1;
            }
        }
    }
 
    for (int i = 2; i <= M; i++)
    {
        for (int j = 2; j <= N; j++)
        {
            // 목장일 지을 수 있는 땅일 때
            if (land[i][j] == 0)
            {
                // 정사각형을 선 목장과 합쳐서 만들 수 있으면 합쳐서 만든다
                if (land[i - 1][j - 1] == 0 && land[i - 1][j] == 0 && land[i][j - 1] == 0)
                {
                    dp[i][j] = minfunc(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])+1;
                }
                // 정사각형을 선 목장과 합쳐서 만들 수 없으면 1을 넣는다.
                else
                {
                    dp[i][j] = 1;
                }
            }
            // 목장을 지을 수 없는 땅일 때
            else
            {
                dp[i][j] = 0;
            }
        }
    }
 
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            ans = max(ans, dp[i][j]);
        }
    }
 
    cout << ans;
 
    return 0;
}