[BOJ 1028, C++] 다이아몬드 광산

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

1028번: 다이아몬드 광산

 

풀이

문제 풀이 아이디어는 의외로 쉽습니다.

위, 아래, 오른쪽, 왼쪽 꼭지점이 있는데, 여기서 오른쪽 꼭지점에서 ↗로 갈 수 있는 최대 길이, ↘로 갈 수 있는 최대 길이를 구해주고, 왼쪽 꼭지점에서 ↖로 갈 수 있는 최대 길이, ↙로 갈 수 있는 최대 길이를 구해주면 됩니다. 그래서 총 4개의 배열이 필요하고 이것을 전부 DP로 구해주면 됩니다.

 

이제 다이아몬드의 최대 크기를 구하는데, 이때 풀이는 2가지로 나뉩니다.

하나는 2중 for문을 이용하여 오른쪽 꼭지점 좌표를 구하고, 그 꼭지점에서 만들 수 있는 최대 길이(min(↗, ↘))를 구해줍니다. 그 후에 저 길이만큼 for문을 돌려주면 됩니다.

다른 방법은 2중 for문을 이용하여 오른쪽 꼭지점 좌표를 구하고, for문을 하나 더 중첩시켜 왼쪽 꼭지점 좌표도 구해서 둘이 마름모를 형성할 수 있는지 구해주면 됩니다.

 

속도가 첫 번째 방법이 두 번째 방법보다 두 배나 빠르므로 첫 번째 방법 코드를 올립니다.

 

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
const int N = 751;
int r, c;
char MAP[N][N];
int dp_up[2][N][N], dp_down[2][N][N]; // 0 오른쪽, 1 왼쪽
 
 
int go_up(int x, int y, int val) {
    if (x < 0 || x >= r || y < 0 || y >= c || MAP[x][y] == '0') return 0;
 
    int& ret = dp_up[1][x][y];
    if (ret != -1) return ret;
 
    dp_up[0][x][y] = val;
 
    return ret = 1 + go_up(x + 1, y - 1, val + 1);
}
 
int go_down(int x, int y, int val) {
    if (x < 0 || x >= r || y < 0 || y >= c || MAP[x][y] == '0') return 0;
 
    int& ret = dp_down[0][x][y];
    if (ret != -1) return ret;
 
    dp_down[1][x][y] = val;
 
    return ret = 1 + go_down(x + 1, y + 1, val + 1);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(dp_up, -1, sizeof(dp_up));
    memset(dp_down, -1, sizeof(dp_down));
 
    cin >> r >> c;
    for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) cin >> MAP[i][j];
 
 
    for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) {
        if (MAP[i][j] == '1') {
            go_up(i, j, 1); go_down(i, j, 1);
        }
    }
 
    int ans = 0;
    for (int i = 0; i < r; i++) for (int j = 0; j < c; j++){
        int x = min(dp_up[0][i][j], dp_down[0][i][j]);
        if (MAP[i][j] == '1') {
            for (int len = 1; len <= x; len++) {
                int k = j + 2 * len - 2;
 
                if (k >= c) break;
                if (MAP[i][k] == '0') continue;
 
                int y = min(dp_up[1][i][k], dp_down[1][i][k]);
                if (y >= len) ans = max(ans, len);
            }
        }
    }
 
    cout << ans << endl;
 
    return 0;
}