[백준 14500] 테트로미노 (DFS) (C/C++) (★)

#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[500][500];
int visited[500][500];
int Max;
int N, M;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1}; // 상하좌우 
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void check(int i, int j)
{
    if(safe(i+1, j+2) == 1)
    {
        int val = map[i][j] + map[i][j+1] + map[i][j+2] + map[i+1][j+1]; // ㅜ 
        
        if(val > Max)
        {
            Max = val;
        }    
    } 
    
    if(safe(i-1, j+2) == 1)
    {
        int val = map[i][j] + map[i][j+1] + map[i][j+2] + map[i-1][j+1]; // ㅗ 
        
        if(val > Max)
        {
            Max = val;
        }    
    } 
    
    if(safe(i+2, j-1) == 1)
    {
        int val = map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j-1]; // ㅓ 
        
        if(val > Max)
        {
            Max = val;
        }    
    }
    
    if(safe(i+2, j+1) == 1)
    {
        int val = map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j+1]; // ㅏ 
        
        if(val > Max)
        {
            Max = val;
        }    
    }
}
 
void DFS(int sum, int x, int y, int cnt)
{
    if(cnt == 4)
    {
        if(sum > Max)
        {
            Max = sum;
        }
        
        return;
    }
    
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0)
        {
            visited[xpos][ypos] = 1;
            DFS(sum + map[xpos][ypos], xpos, ypos, cnt+1);
            visited[xpos][ypos] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B14500_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            visited[i][j] = 1;
            DFS(map[i][j], i, j, 1);
            check(i, j);
            visited[i][j] = 0;
        }
    }
        
    printf("%d", Max);
    
    return 0;
}