알고리즘: 백준 1261번 알고스팟 (feat.python)

 

1261번: 알고스팟

 

import sys
import heapq
read = sys.stdin.readline
m, n = map(int, read().split())
maze = [list(map(int,read().strip()))for i in range(n)]
visit = [[0 for _ in range(m)] for _ in range(n)]

def dijkstra():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    hq = []
    heapq.heappush(hq, [0, 0, 0])
    while hq:
        weight, c_x, c_y = heapq.heappop(hq)
        if visit[c_y][c_x]:
            continue
        visit[c_y][c_x] = 1
        if c_x == m-1 and c_y == n-1:
            return weight
        for i in range(4):
            if 0<= c_x+dx[i] <m and 0<= c_y+dy[i] <n and not visit[c_y+dy[i]][c_x+dx[i]]:
                if maze[c_y + dy[i]][c_x + dx[i]] == 1:
                    heapq.heappush(hq, [weight+1, c_x+dx[i], c_y+dy[i] ])
                else:
                    heapq.heappush(hq, [weight, c_x + dx[i], c_y + dy[i]])

print(dijkstra())