[백준] 14442번: 벽 부수고 이동하기2 파이썬

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

아니 시간초과 라니?

벽 부수고 이동하기 1에서 살짝만 수정하면 될줄 알았는데

... 시간초과라니?

 

파이썬이 느리긴 느린가보다.

파이썬으로 정답인 사람이 아무도 없네

 

pypy3로 바꿔서 제출.

 

....? 시간초과

 

https://www.acmicpc.net/board/view/111938

이 글 보고 배열 차원 선언 순서를 바꿔서 다시 제출하니 성공했다.

배열차원 순서에 따라 이렇게 차이가 나는건 처음 알았다.....

또 배우고 갑니다....

 

코드

import sys
from collections import deque

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

def bfs():
  q = deque()
  q.append((0, 0, 0)) # x, y, 벽 파괴 여부
  dist[0][0][0] = 1
  while q:
    x, y, z = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m:
        if map[nx][ny] == 1 and z < k:
          nz = z + 1
          if dist[nz][nx][ny] == inf:
            dist[nz][nx][ny] = dist[z][x][y] +1
            q.append((nx, ny, nz))
        if map[nx][ny] == 0:
          nz = z
          if dist[nz][nx][ny] == inf:
            dist[nz][nx][ny] = dist[z][x][y]+1
            q.append((nx, ny, nz))

inf = float('inf')
n, m, k = map(int, sys.stdin.readline().split())
map = [list(map(int, list(sys.stdin.readline().strip()))) for _ in range(n)]
dist = [[[inf for _ in range(m)] for _ in range(n)] for _ in range(k+1)]
bfs()
min_path = inf
for i in range(k+1):
  min_path = min(min_path, dist[i][n-1][m-1])
if min_path == inf:
  print(-1)
else:
  print(min_path)