이번 문제는 다익스트라 알고리즘으로 풀 수 있는 문제이다. 우선 그래프를 인접 행렬 형태로 저장하고, 4가지 방향에 대한 탐색을 통하여 그때 그때의 최솟값으로 갱신하는 방식으로 최단거리를 구하였다. 우선 해당 좌표가 -1일 경우에는 접근할 수 없으므로 다음으로 탐색할 수 있는 조건으로 좌표의 값이 -1이 아니고 0<=y<m, 0<=x<m의 범위 안에 있을 경우를 넣어주었다.

• m, n을 입력받는다.
• 그래프로 사용할 리스트 graph를 선언한다.
• m번 반복하는 for문을 돌린다.
  -> graph를 입력받는다.
• graph[0][0]이 -1일 경우, -1을 출력하고 프로그램을 종료시킨다.
• 4가지 방향에 대한 정보를 dy, dx에 짝지어 저장한다.
• 최대값을 저장할 변수 INF에 sys.maxsize를 저장한다.
• 거리를 저장할 리스트 dist를 INF m*n으로 채운다.
• dist[0][0]을 graph[0][0]으로 갱신한다.
• 다익스트라에 사용할 큐 q를 최소힙으로 선언하고 (graph[0][0], 0, 0)을 넣는다.
• q가 존재하는 동안 반복하는 while문을 돌린다.
  -> q에서 cost, y, x를 추출한다.
  -> 만약 cost가 dist[y][x]보다 클 경우, 다음 반복으로 넘어간다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny를 y+dy[i]로 저장한다.
  --> nx를 x+dx[i]로 저장한다.
  --> 만약 ny가 0보다 크거나 같고 m보다 작고, nx가 0보다 크거나 같고 n보다 작고, graph[ny][nx]가 -1이 아닐 경우,
  ---> nxt_cost를 cost+graph[ny][nx]로 저장한다.
  ---> 만약 nxt_cost가 dist[ny][nx]보다 작을 경우,
  ----> dist[ny][nx]를 nxt_cost로 갱신한다.
  ----> q에 (nxt_cost, ny, nx)를 넣는다.
• 만약 dist[m-1][n-1]이 INF와 같을 경우, -1을 출력한다.
• 그 외에는 dist[m-1][n-1]을 출력한다.

Code

import sys
import heapq
m, n=map(int, input().split())
graph=[]
for _ in range(m):
    graph.append(list(map(int, input().split())))
if graph[0][0]==-1:
    print(-1)
    quit()
dy=[0, 0, -1, 1]
dx=[-1, 1, 0, 0]
INF=sys.maxsize
dist=[[INF]*n for _ in range(m)]
dist[0][0]=graph[0][0]
q=[]
heapq.heappush(q, (graph[0][0], 0, 0))
while q:
    cost, y, x=heapq.heappop(q)
    if cost>dist[y][x]:
        continue
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<m and 0<=nx<n and graph[ny][nx]!=-1:
            nxt_cost=cost+graph[ny][nx]
            if nxt_cost<dist[ny][nx]:
                dist[ny][nx]=nxt_cost
                heapq.heappush(q, (nxt_cost, ny, nx))
if dist[m-1][n-1]==INF:
    print(-1)
else:
    print(dist[m-1][n-1])