백준 14442 - 벽 부수고 이동하기 2 (Python)

https://acmicpc.net/problem/14442 

14442번: 벽 부수고 이동하기 2

1600과 동일하다. 부순 벽의 개수를 기록해두자.

Python3로는 풀 수 없다. pypy3만 가능하니 참고하도록 하자.

from collections import deque
import sys
input=sys.stdin.readline
INF=sys.maxsize
N,M,K=map(int,input().split())
dy=[1,-1,0,0]
dx=[0,0,1,-1]
visited=[[[-1]*(K+1) for _ in range(M)] for _ in range(N)]
graph=[[int(i) for i in list(input().strip())] for _ in range(N)]

if M==1 and N==1:
    print(1)
    exit(0)


def bfs():
    q=deque([(0,0,1,K)])
    visited[0][0][K]=1
    while q:
        c_y,c_x,c_v,c_k=q.popleft()
        for i in range(4):
            ny=c_y+dy[i]
            nx=c_x+dx[i]
            nk=c_k-1
            if 0<=ny<N and 0<=nx<M:
                if nk>=0 and graph[ny][nx]==1 and visited[ny][nx][nk]==-1:
                    q.append((ny, nx, c_v + 1, nk))
                    visited[ny][nx][nk] = c_v + 1

                elif graph[ny][nx]!=1 and visited[ny][nx][c_k]==-1:
                    q.append((ny,nx,c_v+1,c_k))
                    visited[ny][nx][c_k]=c_v+1


bfs()
ans=INF

for i in visited[N-1][M-1]:
    if 0<i:
        ans=min(i,ans)

else:
    print(ans if ans!=INF else -1)