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

 

 

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

1028번: 다이아몬드 광산

 

입력 내에서 가장 큰 다이아몬드 모양의 길이를 출력하는 문제이다. 문제 해결을 위해선 공통적으로, 대각선 길이에 대한 아이디어가 필요하다.

 

 

 

---

 

문제의 핵심은 grid[i][j]로부터 뻗어나오는 대각선의 길이를 배열에 저장하는 것이다. 이 과정에서 Dinamic Programming을 사용하고, 이후는 다양한 방법으로 접근할 수 있다.

DP_D[2][i][j], DP_U[2][i][j]를 만들었다. 각각은 연속된 1의 개수를 의미한다.

 

DP_D[0] = ↘  //  DP_D[1] = ↙

DP_U[0] = ↖  //  DP_U[1] = ↗

 

1. 입력을 받으며 DP_U와 DP_D를 구한다

2. 3중 반복문을 돌리면서 최대 길이를 갱신한다

 

---

 

 

// ANSWER

#include <iostream>
#include <algorithm>
using namespace std;

int grid[760][760];
int DP_D[2][760][760];  //  연속된1의개수  //  0 = ↘  //  1 = ↙
int DP_U[2][760][760];  //  연속된1의개수  //  0 = ↖  //  1 = ↗

int main(){
    int R, C;
    int ans = 0;
    
    scanf("%d %d", &R, &C);
    
    for (int i = 1 ; i <= R ; i ++){  //입력받으며 DP_U 생성
        for (int j = 1 ; j <= C ; j ++){
            scanf("%1d", &grid[i][j]);
            if (grid[i][j] == 1) {
                DP_U[0][i][j] = DP_U[0][i - 1][j - 1] + 1;
                DP_U[1][i][j] = DP_U[1][i - 1][j + 1] + 1;
            }
            else {
                DP_U[0][i][j] = 0;
                DP_U[1][i][j] = 0;
            }
        }
    }

    for (int i = R ; i >= 0 ; i --){  //역순. DP_D 생성
        for (int j = C ; j >= 0 ; j --){
            if (grid[i][j] == 1) {
                DP_D[0][i][j] = DP_D[0][i + 1][j - 1] + 1;
                DP_D[1][i][j] = DP_D[1][i + 1][j + 1] + 1;
            }
            else {
                DP_D[0][i][j] = 0;
                DP_D[1][i][j] = 0;
            }
        }
    }
    
    
    for (int i = 1; i <= R; i++){
        for (int j = 1; j <= C; j++){  //모든 좌표에 대해 검사
            int tmp1 = min(DP_D[0][i][j], DP_D[1][i][j]);
            for (int len = 1; len <= tmp1; len++) {  
            //해당 좌표에서 가능한 모든 길이를 알기 위해, 반복문으로 검사
                int k = (len - 1) * 2;
                
                int tmp2 = min(DP_U[0][i+k][j], DP_U[1][i+k][j]);
                if (tmp2 >= len) ans = max(ans, len);
            }
        }
    }
    
    printf("%d", ans);
    
}