백준 14442. 벽 부수고 이동하기 2

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

import sys
from collections import deque
input = sys.stdin.readline

n, m, k = map(int,input().split())  # 세로, 가로, 벽 부수기 횟수
arr = [list(input().rstrip()) for _ in range(n)]
visited = [[[0] * m for _ in range(n)] for _ in range(k+1)]  # (벽 부술 수 있는 횟수, 행, 열)

def bfs():
    q = deque([(k, 0, 0)])  # (남은 벽 부수기 횟수, x, y)
    visited[k][0][0] = 1  # 시작 지점 방문 처리 (최초 거리 1)

    while q:
        crash, i, j = q.popleft()

        # 도착점에 도달하면 결과 반환
        if i == n - 1 and j == m - 1:
            return visited[crash][i][j]

        for di, dj in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            ni, nj = i + di, j + dj

            if 0 <= ni < n and 0 <= nj < m:
                # 벽이 아닐 때
                if arr[ni][nj] == '0' and not visited[crash][ni][nj]:
                    visited[crash][ni][nj] = visited[crash][i][j] + 1
                    q.append((crash, ni, nj))

                # 벽을 부술 수 있고, 아직 방문하지 않은 경우
                elif arr[ni][nj] == '1' and crash > 0 and not visited[crash - 1][ni][nj]:
                    visited[crash - 1][ni][nj] = visited[crash][i][j] + 1
                    q.append((crash - 1, ni, nj))

    return -1  # 도달할 수 없는 경우

print(bfs())

[체크포인트]

elif문에서 벽을 부술 수 있는 경우 방문 검사할 때 crash -1 한 걸로 검사해야됨!

그리고 수가 적은 쪽이 맨 앞에 오는 것이 시간, 메모리 훨씬 절약된다고 한다...

ex) visited[1000][100][1]보다 visited[1][100][1000]이 더 좋음

그래서 crash를 맨 앞으로 배치...