https://acmicpc.net/problem/14500

풀이

ㅗ자 모양 블록을 제외한 경우 모두 브루트포스를 사용해 상하좌우 dfs 탐색을 이용하여 만들 수 있는 블록이다. 따라서 depth가 4, 즉 블록 크기가 4인 경우에 answer을 업데이트한다.
반면 ㅗ자 모양 블록은 상하좌우 dfs 탐색으로만은 탐색할 수 없다. 따라서 special 이라는 함수를 따로 만들고, sx, sy 방향을 각각 지정해주어 탐색을 진행하였다.

from collections import deque

N,M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

answer = 0
visited = [[0]*M for _ in range(N)]


def dfs(depth, sum, x, y):
    global answer

    if depth == 4:
        answer = max(sum, answer)
        return

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<=nx<N and 0<=ny<M and not visited[nx][ny]:
            visited[nx][ny] = 1
            dfs(depth+1, sum+arr[nx][ny], nx, ny)
            visited[nx][ny] = 0


sx = [(0,0,0,1), (0,0,0,-1), (0,-1,1,0), (0,-1,1,0)]
sy = [(0,-1,1,0), (0,-1,1,0), (0,0,0,-1), (0,0,0,1)]


def special(x, y):
    global answer

    for i in range(4):
        tmp = 0
        for j in range(4):
            nx = x+sx[i][j]
            ny = y+sy[i][j]

            if 0<=nx<N and 0<=ny<M:
                tmp += arr[nx][ny]
            else:
                tmp = 0
                break

        answer = max(tmp, answer)


for i in range(N):
    for j in range(M):
        visited[i][j] = 1
        dfs(1, arr[i][j], i, j)
        visited[i][j] = 0

        special(i,j)

print(answer)