이번 문제는 DFS를 활용하여 해결할 수 있는 문제였다. 보라색 테트로미노를 제외한 테트로미노들은 그래프 이론을 통해 확인이 가능하다. 그래서 보라색 테트로미노는 따로 확인을 실시했다.

• DFS의 인자로 y, x, sum, cnt를 주었다. sum은 테트로미노가 올라간 자리의 수들의 합을 저장하는 인자이고, cnt는 몇번 확인했는지를 저장하는 인자이다.
• cnt가 3이면 하나의 테트로미노를 확인한 것이므로 새로 시작해야 한다.
• 보라색 도형의 모든 경우를 확인하기 위해서는 보라색 도형이 회전한 경우까지 모두 확인해야한다. 이를 s1, s2, s3, s4로 나타냈다.
• DFS로 4개의 테트로미노를 확인하고, s1, s2, s3, s4로 보라색 테트로미노를 확인한다. 이 과정의 시작점은 n x m 모든 경우로 두고 전부 확인한다.

Code

#include <iostream>
#include <cstring>
#define MAX 501
using namespace std;

int n,m;
int map[MAX][MAX];
bool visited[MAX][MAX];
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
int result=0;

int Big(int a, int b){
    if(a>b)
        return a;
    return b;
}
void Input(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>map[i][j];
        }
    }
}

void DFS(int y, int x, int sum, int cnt){
    visited[y][x]=true;
    if(cnt==3){
        result=Big(result, sum);
        return;
    }
    for(int i=0; i<4; i++){
        int ny=dy[i]+y;
        int nx=dx[i]+x;
        if(nx<0||ny<0||ny>=n||nx>=m)
            continue;
        if(visited[ny][nx])
            continue;
        
        DFS(ny, nx, sum+map[ny][nx], cnt+1);
        visited[ny][nx]=false;
    }
}

void s1(int y, int x){
    int tsum=0;
    tsum=map[y][x]+map[y][x+1]+map[y][x+2]+map[y-1][x+1];
    if(tsum>result)
        result=tsum;
}

void s2(int y, int x){
    int tsum=0;
    tsum=map[y][x]+map[y][x+1]+map[y][x+2]+map[y+1][x+1];
    if(tsum>result)
        result=tsum;
}

void s3(int y, int x){
    int tsum=0;
    tsum=map[y][x]+map[y+1][x]+map[y+2][x]+map[y+1][x+1];
    if(tsum>result)
        result=tsum;
}

void s4(int y, int x){
    int tsum=0;
    tsum=map[y][x]+map[y-1][x+1]+map[y][x+1]+map[y+1][x+1];
    if(tsum>result)
        result=tsum;
}

void Solution(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            memset(visited, false, sizeof(visited));
            DFS(i, j, map[i][j], 0);
            if(i-1>=0&&j+2<m) s1(i,j);
            if(i+1<n&&j+2<m) s2(i,j);
            if(i+2<n&&j+1<m) s3(i,j);
            if(i+1<n&&i-1>=0&&j+1<m) s4(i,j);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    cout<<result<<endl;
    return 0;
}