백준 1261 알고스팟 (파이썬)

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

벽을 부수는 횟수를 가중치로 생각하여 다익스트라를 수행한다

목표값에 도달하였을 때의 부순 횟수를 출력하면 부순 벽의 최소값이 된다

from heapq import heappush, heappop
import sys

input = sys.stdin.readline
INF = sys.maxsize

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

def dij():
    heappush(q, [0, 0, 0])
    d[0][0] = 1
    while q:
        w, x, y = heappop(q)
        if x == m-1 and y == n-1:
            print(w)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                nw = w + a[nx][ny]
                if nw < d[nx][ny]:
                    d[nx][ny] = nw
                    heappush(q, [nw, nx, ny])

n, m = map(int, input().split())
a = [list(map(int, input().strip())) for _ in range(m)]
d = [[INF]*n for _ in range(m)]
q = []

dij()