백준 1261 : 알고스팟 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

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

def Dijkstra():

    heap=[] ; heapq.heappush(heap,(0,0,0))
    dp[0][0]=0

    while heap:

        value,x,y=heapq.heappop(heap)

        if dp[x][y]<value:
            continue

        for i in range(4):
            nx=x+dx[i] ; ny=y+dy[i]
            if 0<=nx<M and 0<=ny<N:

                if value+graph[nx][ny]<dp[nx][ny]:
                    dp[nx][ny]=value+graph[nx][ny]

                    heapq.heappush(heap,(value+graph[nx][ny], nx , ny))

    return dp[M-1][N-1]

INF=int(1e9)
N,M=map(int,input().split())

graph=[ list(map(int,input().rstrip())) for _ in range(M)]

dp=[ [INF]*(N+1) for _ in range(M+1) ]

print( Dijkstra() )

📌 어떻게 접근할 것인가?

다익스트라를 이용해 풀었습니다. 그래프의 x 와 y 좌표를 저장하고 heapq 를 통해 그래프의 값이 0 인 지점을 우선적으로 넣어주었습니다. 그리고 이동가능한 모든 정점에 대해서 매번 최소값을 갱신해주면서 이동을 하고 마지막에 dp[M-1][N-1] 을 출력하면 답이 됩니다.