[백준 알고리즘] 1028번 다이아몬드 광산 C++

왼쪽아래로 내려가는 대각선과 오른쪽 아래로 내려가는 대각선

다이아몬드 형식의 위 특성을 활용해서 ld, rd배열에 각 위치에서 최대로 뻗을 수 있는 대각선의 크기를 저장한다.

이후 ld rd의 값이 둘 다 0이 아닐때,

2~ min(ld값, rd값)의 길이(n)을 갖는 다이아몬드가 생성 가능한지 확인 한다.

 다이아몬드 생성가능 여부는 왼쪽 대각선을 내렸을때 좌표의 rd값이 n이상이면서, 

오른쪽 대각선을 내렸을때 좌표의 ld값이 n이상인지 확인한다.

 

(다이나믹 프로그래밍)

#include <iostream>

using namespace std;

int main(){
	int r, c, res =0;

	cin >> r >> c;

	int ld[r][c], rd[r][c];

	char input; 

	for(int i=0; i<r; i++)
		for(int j=0; j<c; j++){
			cin >> input;
			if(input == '0'){
				ld[i][j] = 0;
				rd[i][j] = 0;
			}
			else{
				ld[i][j] = 1;
				rd[i][j] = 1;
			}
		}

	for(int i=r-2; i>=0; i--){
		for(int j=0; j<c; j++){
			if(ld[i][j] == 1 && j!= 0){
				ld[i][j] += ld[i+1][j-1];
			}
			if(rd[i][j] ==1 && j!= c-1){
				rd[i][j] += rd[i+1][j+1];
			}
		}
	}

	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			if(ld[i][j] !=0 && rd[i][j] !=0){
				res = max(res, 1);
				if(ld[i][j] != 1 && rd[i][j] != 1){
					int n = min(ld[i][j], rd[i][j]);
					while(n > 1){
						if(rd[i+n-1][j-n+1] >= n && ld[i+n-1][j+n-1]>=n){
							res = max(res, n);
						}
						n --;
					}
				}
			}
		}
	}
	cout << res << endl;
	return 0;
}