[Python/파이썬] - 백준(BOJ) 14442번 : 벽 부수고 이동하기 2

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

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

 

BFS로 (0,0)에서 시작하여 (n-1, m-1)에 도착할 때 까지 K개 이하의 벽을 부수고 진행하면 된다.

vst, brk 배열을 생성하여 각각 이동 블록 개수와 부순 벽 개수를 저장하고 brk가 k를 넘으면 멈추게 한다.

시간을 줄이기 위해 이동할 블록이 현재 블록보다 부순 벽 개수가 적고 이동 거리도 적으면 탐색하지 않도록 하였다.

 

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

def bfs():
    while queue:
        y, x = queue.popleft()
        for i in range(4):
            yy = y + dy[i]
            xx = x + dx[i]
            if 0 <= yy < n and 0 <= xx < m:
                if yy == n-1 and xx == m-1:
                    print(vst[y][x]+1)
                    return
                if arr[yy][xx] == 1:
                    if brk[yy][xx] <= brk[y][x]+1 and vst[yy][xx] <= vst[y][x]+1:
                        continue
                    if brk[y][x]+1 > k:
                        continue
                    vst[yy][xx] = vst[y][x]+1
                    brk[yy][xx] = brk[y][x]+1
                    queue.append([yy, xx])

                else:
                    if brk[yy][xx] <= brk[y][x] and vst[yy][xx] <= vst[y][x]+1:
                        continue
                    vst[yy][xx] = vst[y][x]+1
                    brk[yy][xx] = brk[y][x]
                    queue.append([yy, xx])
    print(-1)

n, m, k = map(int,input().split())
arr = [list(map(int, input().strip())) for _ in range(n)]
vst = [[sys.maxsize for _ in range(m)] for _ in range(n)]
brk = [[0 for _ in range(m)] for _ in range(n)]
dy = [0,1,0,-1]
dx = [1,0,-1,0]
queue = deque([[0, 0]])
vst[0][0] = 1
if n == 1 and m == 1:
    print(1)
else:
    bfs()