[백준] 알고스팟.py

import sys
import heapq
N, M = map(int, sys.stdin.readline().split())
maps = []
for _ in range(M):
    maps.append(list(sys.stdin.readline()))
visited = [[0 for _ in range(N)] for _ in range(M)]

def bfs(start, maps, visited):
    dirs = [(1,0),(0,1),(0,-1),(-1,0)]
    queue = []
    heapq.heappush(queue, start)
    while queue:
        cnt, y, x = heapq.heappop(queue)
        visited[y][x] = 1
        if y == M - 1 and x == N - 1:
            return cnt
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if 0 <= ny < M and 0 <= nx < N and not visited[ny][nx]:
                visited[ny][nx] = 1
                if maps[ny][nx] == "0":
                    heapq.heappush(queue, (cnt, ny, nx))
                elif maps[ny][nx] == "1":
                    heapq.heappush(queue, (cnt + 1, ny, nx))
        
print(bfs((0,0,0), maps, visited))