[ 문제 ]

https://www.acmicpc.net/problem/1261

[ 알고리즘 유형 ]

그래프 이론
다익스트라

[ 정답 코드 ]

BFS

# BFS 벽을 최소 몇 개 부수어야 하는가?
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]

m,n = map(int, input().split())
arr = [ list(map(int, input())) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]  # 가중치

q = deque()
q.append((0,0))
dist[0][0] = 0
while q:
    x,y = q.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < n and 0 <= ny < m:
            if dist[nx][ny] == -1:
                if arr[nx][ny] == 0:
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
                else:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
print(dist[n-1][m-1])

[ 풀이 방법 ]

미로탐색과 유사
다른점은 벽을 부수는 최소 회수
가중치는 벽을 부순 횟수와 같다.
0->0 가중치:0
0->1 가중치:1
1->1 가중치:1

즉, 덱을 이용하여 가중치가 0일 때는, appendleft
가중치가 1일 때는 append 하면
벽을 최소로 부수는 개수를 찾을 수 있다.