미로 탈출

p.152

from collections import deque

n,m = map(int, input().split())
graph=[]
visited=[[False]*m for _ in range(n)]

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

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

def bfs(x,y):
  queue=deque()
  queue.append((x,y))
  visited[x][y]=True

  while queue:
    x,y=queue.popleft()
    
    for i in range(4): #상하좌우 확인
      nx=x+dx[i]
      ny=y+dy[i]
      
      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      elif graph[nx][ny]==0:
        continue
      elif visited[nx][ny]==True:
        continue
      elif graph[nx][ny]==1:
        queue.append((nx,ny))
        print(nx,ny)
        visited[nx][ny]=True
        graph[nx][ny]=graph[x][y]+1

  return graph[n-1][m-1]


print(bfs(0,0))