이번 문제는 BFS를 활용하여 해결하였다. 0이 아닌 모든 좌표에서 시작하여 더 이상 움직일 수 없을 때까지 BFS를 통해 이동시켜 이때의 길이와 시작+끝의 값을 결과 리스트에 저장하고, 결과 리스트를 길이, 시작+끝의 내림차순으로 정렬하여 가장 앞의 값을 출력하도록 하여 해결하였다. n과 m의 범위가 50이었기 때문에 이러한 풀이가 가능했던것 같다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
answers = []
def bfs(sy, sx):
    q = deque()
    q.append((sy, sx, 0))
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[sy][sx] = True
    while q:
        y, x, cnt = q.popleft()
        flag = False
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] > 0 and not visited[ny][nx]:
                flag = True
                visited[ny][nx] = True
                q.append((ny, nx, cnt+1))
        if not flag:
            answers.append((cnt, grid[sy][sx]+grid[y][x]))
for i in range(n):
    for j in range(m):
        if grid[i][j] > 0:
            bfs(i, j)
answers.sort(key=lambda x:(x[0], x[1]), reverse=True)
print(answers[0][1])