이코테의 미로 탈출 문제와 완전히 동일하다.
이 문제 또한 bfs()를 이용해주면 되는데, 가장 왼쪽 상단 지점부터 시작하여 bfs()를 수행해 이동 가능한 칸을 차례차례 방문한다.
이 때 방문 여부와 이동 거리를 표시하기 위해, 특정 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 arr의 현재 좌표 값으로 갱신해주면 된다.
# 상하좌우 1이있으면 갈 곳이 있다는 뜻이고,
# 계속 누적해서 움직이면 됨
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
for _ in range(n):
arr.append(list(map(int, input().strip())))
d = [(0, -1), (0, 1), (1, 0), (-1, 0)]
def bfs(y, x):
q = deque()
q.append((y, x))
while q:
y, x = q.popleft()
for dy, dx in d:
Y, X = y + dy, x + dx
if (0 <= Y < n) and (0 <= X < m) and arr[Y][X] == 1:
q.append((Y, X))
arr[Y][X] = arr[y][x] + 1 # 방문 및 현재까지 지나간 칸 수(이동 거리)를 의미
bfs(0, 0)
print(arr[n - 1][m - 1])