[백준 1028] 다이아몬드 광산

문제

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

 

알고리즘

DP

 

풀이

2차원 광산이 주어질 때, 광산의 최대 크기를 구하는 문제입니다.

 

단순하게 브루트포스로 접근한다면 임의의 점을 광산의 최상단으로 잡은 후 네 변이 만들어 질 수 있나 검사를 해보면 됩니다. 모든 점을 최상단으로 검사하기 위해서는 $O(RC)$ 의 시간복잡도가 필요하고 추가적으로 네 변을 검사하기 위해서 선형시간만큼의 복잡도가 더 필요합니다. 

 

위 계산법에서 낭비되는 부분을 줄여야합니다. 최상단 점 (i, j)에서 len 길이를 만들 때 오른쪽 상단변을 계산하는 과정은 (i+1,j+1)에서 len-1 길이를 만들 때 오른쪽 상단변을 계산하는 과정과 겹치게 됩니다. 즉 DP를 이용합시다.

 

$lcache[i][j]$ : i, j에서 왼쪽으로 만들 수 있는 최대 길이

$rcache[i][j]$: i, j에서 오른쪽으로 만들 수 있는 최대 길이

 

이 배열을 선언하면 광산의 만들어지는 네 점을 빠르게 검사할 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXR = 750 + 5;

int R, C, ans, arr[MAXR][MAXR], rcache[MAXR][MAXR], lcache[MAXR][MAXR];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> R >> C;
    REP(i, R)
    REP(j, C) {
        char x;
        cin >> x;
        arr[i][j] = (x == '1' ? 1 : 0);
    }
    for (int i = R; i >= 1; --i)
        for (int j = C; j >= 1; --j) {
            if (!arr[i][j]) continue;
            rcache[i][j] = rcache[i + 1][j + 1] + arr[i][j];
        }

    for (int i = R; i >= 1; --i)
        for (int j = C; j >= 1; --j) {
            if (!arr[i][j]) continue;
            lcache[i][j] = lcache[i + 1][j - 1] + arr[i][j];
        }

    for (int len = 375; ~len; --len) {
        REP(i, R) {
            if (i + 2 * len - 2 <= R) {
                REP(j, C) {
                    if (j - len + 1 >= 1 && j + len - 1 <= C) {
                        if (rcache[i][j] >= len && lcache[i + len - 1][j + len - 1] >= len && lcache[i][j] >= len && rcache[i + len - 1][j - len + 1] >= len) {
                            cout << len;
                            return 0;
                        }
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}