[BOJ] 2206번 벽 부수고 이동하기 python

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

문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

input 1
6 4
0100
1110
1000
0000
0111
0000

output 1
15

input 2
4 4
0111
1111
1111
1110

output 2
-1

import sys

def bfs():
    q = [[0, 0, 1]]
    visited[0][0][1] = 1

    if n == 1 and m == 1:
        return 1

    while len(q) != 0:
        pos = q.pop(0)
        x = pos[0]
        y = pos[1]
        z = pos[2]

        if x == n - 1 and y == m - 1:
            return visited[x][y][z]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < n and -1 < ny < m:
                if arr[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    q.append([nx, ny, z])
                if arr[nx][ny] == 1 and z == 1:
                    visited[nx][ny][0] = visited[x][y][z] + 1
                    q.append([nx, ny, 0])
    return -1

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
input = sys.stdin.readline
n, m = map(int, input().split())
arr = [list(map(int, list(input().strip()))) for _ in range(n)]
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

print(bfs())

14502번 연구소 문제와 비슷하게 풀면 되겠다고 생각했지만 시간 초과가 나왔다. 결국 다른 풀이에서 아이디어를 얻어 어찌저찌 통과는 했다.