백준 2178: 미로탐색 해설- python

✏️ 문제

2178번: 미로 탐색

 

✏️ 풀이

미로에서 최단거리를 구하는 문제다. 최단거리를 구하는 탐색문제의 경우 BFS가 적합하다.

 

from collections import deque
n,m=map(int,input().split())
matrix=[]
for _ in range(n):
  matrix.append(list(map(int,input())))

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

def bfs(a,b):
  queue=deque([[a,b]])
  while(queue):
    x,y=queue.popleft()
    for i in range(4):
      xx=x+dx[i]
      yy=y+dy[i]
      if 0<=xx<n and 0<=yy<m and matrix[xx][yy]==1:
        queue.append([xx,yy])
        matrix[xx][yy]=matrix[x][y]+1

bfs(0,0)
print(matrix[n-1][m-1])