[백준] 1261 알고스팟

BFS+최단경로(다익스트라)였던 문제
입력을 문자열로 받았는데 '1'이 아닌 1로 체크해서 풀이에서 오답이 나왔었다.

import heapq

dx=[0,1,0,-1]
dy=[1,0,-1,0]
width,height=map(int,input().split())
distance=[[-1]*width for _ in range(height)]
board=[]
for i in range(height):
    board.append(input())

def dijackstra(x,y):
    q=[]
    heapq.heappush(q,(0,x,y))
    while q:
        cnt,x,y=heapq.heappop(q)
        distance[x][y]=0
        if x==height-1 and y==width-1:
            print(cnt)
            return 
        for i in range(4):
            nx=dx[i]+x
            ny=dy[i]+y
            if nx<0 or ny<0 or nx>=height or ny>=width:
                continue
            if distance[nx][ny]!=-1:
                continue
            if board[nx][ny]=='1':
                distance[nx][ny]=distance[x][y]+1
                heapq.heappush(q,(cnt+1,nx,ny))
            else: 
                distance[nx][ny]=distance[x][y]+1
                heapq.heappush(q,(cnt,nx,ny))


dijackstra(0,0)