이번 문제는 BFS를 이용하여 해결하였다. 처음에는 벽을 부수는 모든 경우를 백트레킹을 통해 구하고, 이를 적용하여 각각의 경우마다 탐색을 하도록 하였다. 그러나 이 방법은 시간초과가 발생하였다. 그래서 한번의 BFS를 통해 해결해야겠다고 생각하였고, 벽을 만났을 때, 현재 부순 벽의 수가 k보다 작다면 부수고 이동하도록 하는 방식을 적용하였다. 이때 방문처리는 3차원 리스트를 활용하여 벽을 몇개 부셨을 때의 방문 여부를 체크하도록 하였다.

Code

처음 제출 코드 (시간초과)

from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m, k = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
walls = []
for i in range(n):
    for j in range(m):
        if grid[i][j] == '1':
            walls.append((i, j))
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
combs = []
def broken_walls(cur, comb):
    if cur == len(walls):
        if len(comb) <= k:
            combs.append(comb)
        return
    if len(comb) > k:
        return
    broken_walls(cur+1, comb+[walls[cur]])
    broken_walls(cur+1, comb)
def move(comb):
    q = deque()
    q.append((0, 0, 1))
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[0][0] = True
    while q:
        y, x, dist = 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 (grid[ny][nx] == '0' or (ny, nx) in set(comb)) and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append((ny, nx, dist+1))
    return 1e9
answer = 1e9
broken_walls(0, [])
for comb in combs:
    dist = move(comb)
    answer = min(answer, dist)
if answer == 1e9:
    print(-1)
else:
    print(answer)

정답 코드

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]
def move():
    q = deque()
    q.append((0, 0, 1, 0))
    visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(k+1)]
    visited[0][0][0] = True
    while 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:
                if grid[ny][nx] == '1' and cnt < k and not visited[cnt+1][ny][nx]:
                    visited[cnt+1][ny][nx] = True
                    q.append((ny, nx, dist+1, cnt+1))
                if grid[ny][nx] == '0' and not visited[cnt][ny][nx]:
                    visited[cnt][ny][nx] = True
                    q.append((ny, nx, dist+1, cnt))
    return -1
print(move())