BOJ 16933 벽 부수고 이동하기 3(Python 3)

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

밤에만 벽을 부술 수 있는 점에 주의하면 됩니다.

파이썬은 heapq로 하면 시간 초과가 나옵니다.

deque를 이용해서 다익스트라 비슷하게 풀면 됩니다.

큐에 5개의 값을 넣어주는데 n, m, k, S[n][m][k], 낮/밤 입니다.

Python3으로 제출하면 시간 초과가 나오니 Pypy3으로 제출하면 됩니다.

코드 확인

from collections import deque
input=__import__('sys').stdin.readline
n,m,k=map(int,input().split())
D=[input() for _ in range(n)]
q=deque([(0,0,0,1,0)])
S=[[[float('inf')]*(k+1) for __ in range(m)] for _ in range(n)]
dx,dy=[0,0,1,-1],[1,-1,0,0]
S[0][0][0]=1
while q:
    x,y,z,t,d=q.popleft()
    if S[x][y][z]!=t:continue
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if D[nx][ny]=='0' and S[nx][ny][z]>t+1:
                S[nx][ny][z]=t+1
                q.append((nx,ny,z,t+1,(d+1)%2))
            if z<k and D[nx][ny]=='1':
                if d==0 and S[nx][ny][z+1]>t+1:
                    S[nx][ny][z+1]=t+1
                    q.append((nx,ny,z+1,t+1,(d+1)%2))
                if d==1 and S[nx][ny][z+1]>t+2:
                    S[nx][ny][z+1]=t+2
                    q.append((nx,ny,z+1,t+2,d))
k=min(S[n-1][m-1])
print([k,-1][k==float('inf')])