첫 달 때 queue를 사용해서 미로 찾기 문제를 풀어봐서 그런지 기억이 나서 수월하기 풀었다.

사실 금요일에 푼건 아니고 할머니 생신때문에 집에 계속 없었어서 토요일날 두문제를 풀기로 했다.

y, x 좌표를 업데이트 해주는 dy, dx 와 visit했으면 다시 que에 집어넣지 않는 maze_bool (visited) 리스트를 만들어서 확인해가면서 푼다.

import sys
from collections import deque
sys.stdin = open('input.txt')
input = sys.stdin.readline

Y, X = map(int, input().split())
maze = [list(map(int, input().strip())) for _ in range (Y)]

maze_bool = [[False for _ in range (X)] for _ in range (Y)]
maze_bool[0][0] = 1

que = deque([(0,0)])

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

while maze_bool[Y-1][X-1] == False:
    prev_y, prev_x = que.popleft()
    for i in range (4):
        new_y, new_x = prev_y + dy[i], prev_x + dx[i]
        # 맵 밖으로 나갔거나 (얘네 먼저 확인해줘야함 index error 안뜰려면) maze에 얘네는 못가는 길이거나(0)
        # 아니면 이미 방문했던 길이라 이미 최소 거리가 등록되어있으면 que에 또 넣어줄 필요없다
        if new_y >= Y or new_y < 0 or new_x >= X or new_x < 0 or \\
            maze[new_y][new_x] == 0 or maze_bool[new_y][new_x] != False:
            continue
        else:
            que.append((new_y, new_x))
            maze_bool[new_y][new_x] = maze_bool[prev_y][prev_x] + 1

print(maze_bool[Y-1][X-1])