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

문제

벽 부수고 이동하기 1 문제와 거의 동일하다. 다만 k번까지 부수고 이동할 수 있다는 점을 고려하여 전 문제와 다르게 풀면 될거같다.

풀이

3차원 행렬 n x m x k 로 dp를 만들어주고 bfs를 돌며 카운팅해주며 된다.
만약 인접한 곳이 벽이라면 dp[idx+1][y][x]에 카운트를 저장하고 q에도 idx+1로 넣어준다.
아니라면 dp[idx][y][x]에 카운트 저장하고 q에도 idx로 넣어주면 된다

code

from collections import deque

n,m,k = map(int,input().split())
board = []
for _ in range(n):
    board.append(list(map(int,input())))


dp = [[[-1] * m for _ in range(n)] for _ in range(k+1)]

def bfs():
    q = deque()
    q.append((0,0,0,0))
    dp[0][0][0] = 0
    dy = [0,0,-1,1]
    dx = [-1,1,0,0]
    answer = 9999999
    while q:
        y,x,idx,cnt = q.popleft()
        if y==n-1 and x==m-1:
            answer = min(answer,cnt)
            continue
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if not (0<=ny<n and 0<=nx<m):
                continue
            if dp[idx][ny][nx]!=-1:
                continue
            if board[ny][nx]==0:
                dp[idx][ny][nx]=cnt+1
                q.append((ny,nx,idx,cnt+1))
            else:
                if idx<k:
                    dp[idx+1][ny][nx]=cnt+1
                    q.append((ny,nx,idx+1,cnt+1))
    if answer==9999999:
        return -1
    else:
        return answer+1
print(bfs())

result

시작한 지점도 카운팅 해주는 걸 깜빡해서 2번이나 틀렸다...