14500번 파이썬

아래 방법은 재귀를 이용해서 그런지 시간이나 메모리 소요가 커서 다른 방법을 생각해봐야함!(백준 pypy로 하면 맞춘걸로 나오긴 함)

import sys
input = sys.stdin.readline



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

res=set()
def row_p(ary,num,cnt,row,col,n,m):
    if row < n:
        if [row,col] in ary:
            return
        num+=mat[row][col]
        ary.append([row,col])
        solution(ary,num,cnt+1,row,col,n,m)
        ary.remove([row,col])
    else:
        return
    return
def row_m(ary,num,cnt,row,col,n,m):
    if row >= 0:
        if [row,col] in ary:
            return
        num+=mat[row][col]
        ary.append([row,col])
        solution(ary,num,cnt+1,row,col,n,m)
        ary.remove([row,col])
        
    else:
        return

def col_p(ary,num,cnt,row,col,n,m):
    if col < m:
        if [row,col] in ary:
            return
        num+=mat[row][col]
        ary.append([row,col])
        solution(ary,num,cnt+1,row,col,n,m)
        ary.remove([row,col])
    else:
        return
def col_m(ary,num,cnt,row,col,n,m):
    if col >= 0:
        if [row,col] in ary:
            return
        num+=mat[row][col]
        ary.append([row,col])
        solution(ary,num,cnt+1,row,col,n,m)
        ary.remove([row,col])
    else:
        return

def solution(ary,num,cnt,row,col,n,m):
    #나머지의 경우를 재귀 방식으로 구현(모든 방향으로 한칸 씩 이동시켜봄)
    if cnt > 4:
        res.add(num)
        return
    #ary를 이용한 이유는 앞으로 갔다가 
    #뒤로 -1 다시 해서 제자리로 돌아오는 경우도 cnt를 증가시키는 경우가 있기 때문
    row_p(ary,num,cnt,row+1,col,n,m)
    row_m(ary,num,cnt,row-1,col,n,m)
    col_p(ary,num,cnt,row,col+1,n,m)
    col_m(ary,num,cnt,row,col-1,n,m)


for row in range(N):
    for col in range(M):
        ary=[[row,col]] 
        num = mat[row][col]
        cnt=1
        solution(ary,num,cnt+1,row,col,N,M)
        ary.remove([row,col])

        #ㅗ or ㅜ or ㅓ or ㅏ인 경우
        if (row+1) >= N and (col+1) <M and (row-1) >=0 and (col-1) >=0:
            res.add(num+mat[row][col+1]+mat[row][col-1]+mat[row-1][col])
        elif (col+1) >= M and (row+1) <N and (row-1) >=0 and (col-1) >=0:
            res.add(num+mat[row+1][col]+mat[row][col-1]+mat[row-1][col])
        elif (row+1) < N and (col+1) <M and (row-1) < 0 and (col-1) >=0:
            res.add(num+mat[row+1][col]+mat[row][col-1]+mat[row][col+1])
        elif (row+1) < N and (col+1) <M and (row-1) >=0 and (col-1) < 0:
            res.add(num+mat[row+1][col]+mat[row-1][col]+mat[row][col+1])
        elif (row+1) < N and (col+1) <M and (row-1) >=0 and (col-1) >=0:
            a = num+mat[row][col+1]+mat[row][col-1]+mat[row-1][col]
            b = num+mat[row+1][col]+mat[row][col-1]+mat[row-1][col]
            c = num+mat[row+1][col]+mat[row][col-1]+mat[row][col+1]
            d = num+mat[row+1][col]+mat[row-1][col]+mat[row][col+1]
            res.add(max(a,b,c,d))
        


print(max(res))