https://www.acmicpc.net/problem/2178

풀이

방문한 곳의 좌표와 움직인 횟수를 deque에 넣어주고 다음 순회때 갈 수 있는 4방향을 확인한다.
이미 방문한 곳을 방문하는 것은 최단거리가 아니므로 가지 않는다.

코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
maps = []
for _ in range(n):
    maps.append(list(map(int,input().rstrip())))
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
x, y = 0, 0
count = 1
route = deque([(count, x, y)])
while True:
    cnt, x, y = route.popleft()
    if x==m-1 and y==n-1:
        print(cnt)
        break

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx<0 or ny<0 or nx>=m or ny>=n or maps[ny][nx]!=1:
            continue

        if maps[ny][nx]==1:
            maps[ny][nx] = 2
            route.append((cnt+1,nx,ny))