백준_골드3_2260번(벽 부수고 이동하기)

이번 문제는 기존의 BFS 알고리즘을 사용하고 최단 경로를 도달하는 과정에서 벽을 한 개 까지 부수는 기능을 추가한 최단거리를 추출하는 문제이다. 기존의 BFS알고리즘과 마찬가지로 어떤 노드를 기준으로 동서남북으로 갈 수있는 곳으로 옮기고 최단경로를 구하는데, 벽을 한 개까지 부수는 기능만 추가하면 된다.
먼저 위의 문제에서 행렬로 이뤄진 전체 맵의 각각의 원소는 전 노드에서 벽을 부수는 횟수를 count할 수 없기 때문에, 원소마다 전 노드에서 벽부수는 횟수를 가져와서 진행한다. 그래서 visited 리스트에 전 노드의 벽부수는 횟수에 해당하는 시작부터의 최단 거리를 추가하면서 최단 경로를 계산한다.

from collections import deque
n,m = map(int,input().split())
block_map = []
for i in range(n):
    block_map.append(list(input()))

def bfs(map,n,m):
    need_visited = deque([[0,0,1]])
    visited = [[[0,0] for _ in range(m)] for _ in range(n)]
    visited[0][0] = [1,1]
    control_x = [1,-1,0,0]
    control_y = [0,0,-1,1]
    while need_visited:
        now_x,now_y,boomb = need_visited.popleft()
        if now_x == m - 1 and now_y == n - 1: return visited[now_y][now_x][boomb]
        for i in range(4):
            next_x,next_y = now_x+control_x[i],now_y+control_y[i]
            if -1<next_x<m and -1<next_y<n:
                if visited[next_y][next_x][boomb] ==0 and map[next_y][next_x] == '0':
                    need_visited.append([next_x,next_y,boomb])
                    visited[next_y][next_x][boomb] = visited[now_y][now_x][boomb] + 1
        if boomb > 0:
            for i in range(4):
                next_x,next_y,next_boomb = now_x+control_x[i],now_y+control_y[i],boomb - 1
                if -1<next_x<m and -1<next_y<n:
                    if visited[next_y][next_x][boomb] ==0 and map[next_y][next_x] == '1':
                        need_visited.append([next_x,next_y,next_boomb])
                        visited[next_y][next_x][next_boomb] = visited[now_y][now_x][boomb] + 1
    return -1
print(bfs(block_map,n,m))