[python] 백준 14442 벽 부수고 이동하기 2

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

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

문제 해결

• (0,0)에서 (n-1,m-1)까지 이동하는 문제
• 갈 수 있는 길이 있고 없는 길이 있다. 하지만 예외적으로 k번 갈 수 없는 길을 갈 수 있다.
• 따라서 visited[i][j]에서 예외포인트 k번 까지 가능하다는 것에서 visited[i][j][k]의 방문 여부를 확인하는 것이 편하다.
• visited[i][j][k]의 값은 (i,j)까지 벽을 깰 수 있는 횟수 k번 남기고 이동한 횟수를 말한다.  
• 갈 수 없는 길을 한 번 소비할 때마다 visited[i][j][k]에서 visited[i][j][k-1]이 되고 값도 +1을 처리하면 된다.
• 이렇게 하면 좋은점은 이동횟수 cnt와 벽 부순 횟수 b와 따로 생각하지 않고 그래프로 묶어서 생각할 수 있다는 것이다.
• 사실 python3로 돌리면 시간초과가 나고 pypy3로 돌리면 통과한다. 어떻게 더 줄일 수 있을지는 고민해봐야 하는 상황

 

CODE

import sys
input = sys.stdin.readline
from collections import deque
n,m,k = map(int, input().split())
A = []
for _ in range(n):
    A.append([int(c) for c in str(input().rstrip())])
move = [(0,1),(1,0),(-1,0),(0,-1)]

def bfs():
    que = deque()
    que.append((0,0,k)) # 시작점(0,0), 뚫을 수 있는 벽의 수
    visited = [[[0]*(k+1) for _ in range(m)] for _ in range(n)]
    visited[0][0][k] = 1
    while que:
        r,c,b = que.popleft()
        if r == n-1 and c == m-1:
            return visited[r][c][b]
        for next in move:
            new_r = r + next[0]
            new_c = c + next[1]
            if 0<=new_r<=n-1 and 0<=new_c<=m-1:
                if b>=1 and visited[new_r][new_c][b-1] == 0 and A[new_r][new_c]==1:
                    visited[new_r][new_c][b-1] = visited[r][c][b]+1
                    que.append((new_r,new_c,b-1))
                elif visited[new_r][new_c][b]==0 and A[new_r][new_c] ==0:
                    visited[new_r][new_c][b] = visited[r][c][b]+1
                    que.append((new_r,new_c,b))
    else:
        return -1
ans = bfs()
print(ans)