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

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

1028번: 다이아몬드 광산

 

그다지 어렵지는 않은 DP 문제이다. 다만 한 가지 아이디어가 중요한데, 마름모가 네 변으로 구성되므로 그 네 변의 길이를 brute-force로 구하지 말고 memorization을 사용해서 구하겠다는 아이디어만 내놓으면 된다.

 

나는 먼저 UpRight방향, UpLeft방향, DownRight방향, DownLeft방향에 대해서 그 map을 마지막으로 하는 가장 긴 연속적인 1의 길이를 DP table에 저장하였다. 이 과정에서는 direction * N^2 이 소요되었다. (나중에 따지고 보니 굳이 삼중 for문을 돌릴 필요는 없었다. 2중 for문 안에 모든 direction을 계산해도 된다.)

 

그리고 마름모의 대각선의 길이는 항상 홀수(1,3,5, ...)임에서 착안하여 마름모의 두 대각선이 교차하는 지점에서 양 옆으로 같은 위치에 있는 DP table 중에서, 중심부와 떨어진 거리보다 네 DP table의 min값이 더 큰 경우에는 다이아몬드를 형성할 수 있다고 보고 다이아몬드의 크기를 확인하였다.

 

시간복잡도는

이다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
 
const int maxRC = 800;
const int UL = 1, UR =2, DL =3, DR = 4;
const int DIR = 4;
const int dirRef[5][2] = {{0,0,},{-1,-1},{-1,1},{1,-1},{1,1}};
 
using namespace std;
 
int r, c;
int map[maxRC][maxRC];
int diaRow[DIR+1][maxRC][maxRC];
 
int minAmongFour(int a, int b, int c, int d) {
    if( a<b&&a<c&&a<d) return a;
    else if(b<c&&b<d) return b;
    else if(c<d) return c;
    else return d;
}
 
void findMaxRow() { //네 방향에 대해서 가장 긴 DP table을 찾는 함수
    for(int i = UL; i <= UR; i++) {
        for(int j = 1; j <= r; j++) {
            for(int k = 1; k <= c; k++) {
                if(map[j][k] == 0) diaRow[i][j][k] =0;
                else 
                    diaRow[i][j][k] = max(diaRow[i][j+dirRef[i][0]][k+dirRef[i][1]]+1, 1);
            }
        }
    }
    
    for(int i = DL; i <= DR; i++) {
        for(int j = r; j >= 1; j--) {
            for(int k = 1; k <= c; k++) {
                if(map[j][k] == 0) diaRow[i][j][k] =0;
                else 
                    diaRow[i][j][k] = max(diaRow[i][j+dirRef[i][0]][k+dirRef[i][1]]+1, 1);
            }
        }
    }
    
}
 
 
int findMaxDia() { //DP table을 기반으로 map[i][j]를 중심으로 하는 가장 큰 다이아몬드의 넓이를 리턴하는 함수
    int maxAbleSize;
    int maxDia = 0;
    for(int i = 1; i <= r; i++) { // col
        for(int j = 1; j <= c; j++) { //row
            maxAbleSize = minAmongFour(i,j,r-i+1, c-j+1);
            for(int k = maxAbleSize; k>=1; k--) { //옆으로 확장시키며
                if(diaRow[UL][i][j+k-1] >= k && diaRow[UR][i][j-k+1] >= k &&
                   diaRow[DL][i][j+k-1] >= k && diaRow[DR][i][j-k+1] >= k) { //다 k보다 크다면
                    maxDia = max(maxDia, k);
                    break;
                }
            }
        }
    }
    return maxDia;
}
 
int main(void) {
    
    char tempString[maxRC];
    
    scanf("%d %d", &r, &c);
    
    for(int i = 1; i <= r; i++) {
        scanf("%s", tempString);
        for(int j = 0; j< strlen(tempString); j++) {
            map[i][j+1] = (tempString[j]=='0'? 0:1); 
        }
    }
    
    findMaxRow();
    
    cout<<findMaxDia()<<endl;
    
}

 

 

이 코드는 내 github에서도 확인할 수 있다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1028/1028.cpp

Jordano-Jackson/PS