BOJ 14925 목장 건설하기

사용한 알고리즘

알고리즘 설명

나무와 돌을 포함하지 않는 가장 큰 정사각형을 찾는 문제이다
N x M 크기에 Board에 아무것도 없는 부분은 1, 나무가 있는부분을 -1로 정한다
여기서 문제를 단순화 하기 위해서 Board(i)(j)에 DP 점화식을 정한다.
Board(i)(j) 값은 i, j 에서 왼쪽과 상단에 있는 좌표중 가장 크게 만들수 있는 정사각형 변 길이라고 하자
이 점화식은 다음과 같다
만약 좌표(i, j)에 나무 또는 돌이 있다면,
- board(i)(j) = -1
만약 좌표(i, j)에 나무 또는 돌이 없다면,
- board(i)(j) = min(board(i-1)(j-1), board(i-1)(j), board(i)(j-1)) + 1
이 board(i)(j) 값 중에 최대 값이 정답이다

풀이

// baekjoon 14925 yechan
#include <bits/stdc++.h>
using namespace std;

const int MAX_N=1002;

int N, M, board[MAX_N][MAX_N];

int main() {
    memset(board, -1, sizeof(board));
    scanf("%d%d", &N, &M);

    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            int x; scanf("%d", &x);
            if (x > 0) board[i][j] = -1;
            else board[i][j] = 1;
        }
    }

    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            if (board[i][j] == -1) continue;
            int tmp = min(min(board[i-1][j-1], board[i-1][j]), board[i][j-1]);
            board[i][j] = tmp + 1;
        }
    }

    int ret = 0;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            ret = max(ret, board[i][j]);

    printf("%d\n", ret);
    return 0;
}