[BOJ] 1028 : 다이아몬드 광산

문제 링크

1028번: 다이아몬드 광산 (acmicpc.net)

1028번: 다이아몬드 광산

가장 큰 다이아몬드의 크기를 출력하는 문제.

size 1:    size 2:    size 3:
                         1
              1         1 1
   1         1 1       1   1
              1         1 1
                         1

다이아몬드의 형태는 이러하다.

풀이

문제 분류가 DP 인것을 보고 처음엔 의아했다. 차라리 분할정복문제면 몰라도 이걸 어떻게 DP로 푸는 지 도저히 감이 잡히지 않았다. 구글 속 선배님들의 힌트를 받아서 풀었다.

DP배열에 왼쪽 아래로 최대 대각선의 길이, 오른쪽 아래로 최대 대각선의 길이를 저장하는 것이었다.

Left, Right 라는 2차원 배열을 선언해서 각 점마다 왼쪽, 오른쪽 아래 최대 대각선 길이를 저장해두었다.

이것이 왜 필요하느냐?

특정한 세 점 A,B,C 를 잡아서 A에서의 왼쪽 대각선, 오른쪽 대각선의 길이 B에서의 오른쪽 대각선 길이, C에서의 왼쪽 대각선 길이가 모두 임의의 수 X 이상이면 크기가 i 인 다이아몬드를 만들 수 있다는 뜻이다.

여기서 점 A를 임의로 ( y , x ) 라고 한다면

점 B는 ( y + i - 1, x - ( i - 1 ))로

점 C는 ( y + i - 1, x + (i - 1 ))로 나타낼 수 있다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<ll, int>, int>, vector<pair<pair<ll, int>, int>>, greater<pair<pair<ll, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 750 + 5;
int mine[MAX_N][MAX_N];
int R, C;
int Left[MAX_N][MAX_N];
int Right[MAX_N][MAX_N];
 
bool is_ok(int y, int x) {
    if (y < 0 || y >= R || x < 0 || x >= C)
        return false;
    return true;
}
 
int Find_LD(int y, int x) {
    if (!mine[y][x])
        return 0;
    if (is_ok(y - 1, x + 1) && Left[y - 1][x + 1] > 1)
        return Left[y - 1][x + 1] - 1;
    int ret = 1;
    while (is_ok(y + 1, x - 1)) {
        y++; x--;
        if (mine[y][x])
            ret++;
        else break;
    }
    return ret;
}
 
int Find_RD(int y, int x) {
    if (!mine[y][x])
        return 0;
    if (is_ok(y - 1, x - 1) && Right[y - 1][x - 1] > 1)
        return Right[y - 1][x - 1] - 1;
    int ret = 1;
    while (is_ok(y + 1, x + 1)) {
        y++; x++;
        if (mine[y][x])
            ret++;
        else break;
    }
    return ret;
}
 
int main(void) {
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    cin >> R >> C;
    int ans = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%1d", &mine[i][j]);
            if (mine[i][j])
                ans = 1;
        }
    }
 
    if (ans == 0) {
        cout << "0\n";
        return 0;
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            Left[i][j] = Find_LD(i, j);
            Right[i][j] = Find_RD(i, j);
        }
    }
 
    for (int i = 2; i <= (max(R, C) + 1) / 2; i++) {
        bool chk = false;
        for (int k = 0; k <= R - (2 * i - 2); k++) {
            for (int j = i - 1; j <= C - i + 1; j++) {
                pair<int, int> dot1 = { k,j };
                pair<int, int> dot2 = { k + i - 1, j + i - 1 };
                pair<int, int> dot3 = { k + i - 1, j - (i - 1) };
                if (!is_ok(dot1.first, dot1.second) || !is_ok(dot2.first, dot2.second) || !is_ok(dot3.first, dot3.second))
                    continue;
                if (Left[dot1.first][dot1.second] >= i && Right[dot1.first][dot1.second] >= i
                    && Left[dot2.first][dot2.second] >= i && Right[dot3.first][dot3.second] >= i) {
                    ans = max(ans, i);
                    chk = true;
                    break;
                }
            }
            if (chk)
                break;
        }
    }
    cout << ans << "\n";
    return 0;
}
 

Find_LD() , Find_RD() 함수는 각각 왼쪽, 오른쪽 대각선의 길이를 찾아주는 함수이다.