문제

코드

#2718 : 미로탐색 
import sys
input = sys.stdin.readline
from collections import deque #BFS

m,n = map(int,input().split())

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

queue = deque() #칸수저장 
graph=[]

for i in range(m):
    graph.append(list(map(int, input().rstrip()))) 

#붙이기 

queue.append([0,0]) #0,0에서 출발 

def bfs():
  while queue:
      a,b = queue.popleft() #i.j삽입 
      for i in range(4):
          cx = a+dx[i]
          cy = b+dy[i]
          if 0<=cx<m  and 0<=cy<n and graph[cx][cy]==1: 
              graph[cx][cy] = graph[a][b] + 1 #칸수 더해나감 
              queue.append([cx,cy])
bfs()

print(graph[m-1][n-1])

해설

앞서 푼 토마토 문제와 비슷하다.
그저 시작과 끝을 문제에서 알려줬을 뿐이다.
큐를 만들어서 그 큐에 지나간 칸수를 더하면되는데 시작칸도 포함되므로 토마토와 다르게 1을 안빼주어도 된다.