풀이

처음엔 dfs 방식으로 벽 하나씩 1을 모두 바꿔주는 방식으로 풀이를 했고, 당연히 시간 초과가 떴다.
다음으로 푼 방식은 visited배열과 큐에 벽 부수는 횟수도 추가시켜 3차원 배열을 통해 문제를 풀어주었다. 3차원 배열을 생각해내는게 쉽지 않았다.

from collections import deque
import sys
n, m = map(int, sys.stdin.readline().split())
array = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0,0,-1,1]
# 3차원 리스트 (행, 열, 벽을 깬 여부) 생성
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

def solve(x,y,wall_break_left, visited, array):
    q = deque()
    q.append((x,y,wall_break_left))
    visited[x][y][wall_break_left] = 1

    while q:
        x,y,wall_break_left = q.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y][wall_break_left]
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >= n or ny<0 or ny>=m:
                continue
            # 벽을 깨지 않고 이동
            if array[nx][ny] == 0 and visited[nx][ny][wall_break_left] == 0:
                q.append((nx,ny, wall_break_left))
                visited[nx][ny][wall_break_left] = visited[x][y][wall_break_left] + 1
            # 벽을 깨고 이동
            if array[nx][ny] == 1 and wall_break_left == 1:
                q.append((nx,ny, wall_break_left-1))
                visited[nx][ny][wall_break_left-1] = visited[x][y][wall_break_left] +1
    return -1

print(solve(0,0,1,visited,array))