이번 문제는 BFS를 통해 해결하였다. 기존의 벽 부수고 이동하기 문제에서 낮과 밤에 대한 조건이 추가된 문제였고, 이를 위해 낮과 밤의 정보를 담을 변수 time을 사용했다. time이 1일 경우에는 낮이고, -1일 경우에는 밤인 경우이다. 방문처리는 visited[y좌표][x좌표][부순 벽의 수] 형식으로 진행하였고, 큐에는 (y좌표, x좌표, 거리, 부순 벽의 수)를 담았다. BFS의 while문 안에서 q의 길이만큼 순회하는 for문을 통해 while문 시작 지점에서의 q에 들어있는 모든 원소를 꺼내어 탐색하였다. 범위 확인과 방문처리 여부를 확인하고, 다음 좌표가 0일 경우에는 다음 탐색을 진행하기 위해 큐에 다음 값을 넣어주었고, 1일 경우에는 부순 벽의 수와 방문처리 여부를 확인하고, 낮일 경우에는 벽을 부수고 이동하도록, 밤일 경우에는 현재 좌표에서 한번 기다리도록 구현하였다. 이렇게 for문이 종료되면 밤과 낮을 바꾸기 위해 time에 -1을 곱해주었다.

Code

from collections import deque
n, m, k = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
# 1: 낮, -1: 밤
def move():
    q = deque()
    q.append((0, 0, 1, 0))
    visited = [[[0 for _ in range(k+1)] for _ in range(m)] for _ in range(n)]
    visited[0][0] = [1 for _ in range(k+1)]
    time = 1
    while q:
        for _ in range(len(q)):
            y, x, dist, cnt = q.popleft()
            if (y, x) == (n-1, m-1):
                return dist
            for i in range(4):
                ny, nx = y+dy[i], x+dx[i]
                if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx][cnt]:
                    if grid[ny][nx] == '0':
                        visited[ny][nx][cnt] = dist+1
                        q.append((ny, nx, dist+1, cnt))
                    elif grid[ny][nx] == '1':
                        if cnt+1 <= k and not visited[ny][nx][cnt+1]:
                            if time == 1:
                                visited[ny][nx][cnt+1] = dist+1
                                q.append((ny, nx, dist+1, cnt+1))
                            else:
                                q.append((y, x, dist+1, cnt))
        time *= (-1)
    return -1
print(move())