코드

N,M = map(int,input().split(" "))

graph = [list(map(int, input())) for _ in range(M)]

visited = [[-1 for _ in range(N)] for _ in range(M)]

def bfs(x,y):
    from collections import deque
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    Q = deque([(x,y)])  
    visited[x][y] = 0

    while Q:
        x,y = Q.popleft()
        
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]

            if 0<=nx<M and 0<=ny<N:
                if visited[nx][ny] == -1:
                    if graph[nx][ny] == 0:
                        visited[nx][ny] = visited[x][y]
                        Q.appendleft((nx,ny))

                    elif graph[nx][ny] == 1:
                        visited[nx][ny] = visited[x][y] + 1
                        Q.append((nx,ny))
bfs(0,0)
print(visited[-1][-1])

풀이

• 처음에는 DFS로 풀려고 했으나 시간초과가 날 것 같아서 BFS로 변경
• 만약 visited가 -1이라면 한번도 방문 안한거니 방문처리를 하는데, 그 값이 0이라면 벽을 부술 필요가 없으니 그 전의 vistied 값을 그대로 가져옴
• 값이 1이라면 벽을 부숴야 하므로 직전의 visited에 +1을 해서 저장.
• 벽을 굳이 부술 필요가 없게 0인 곳이 먼저 되도록 appendleft 한다.