[백준] 1261번: 알고스팟 (Python) - 0-1 BFS 탐색

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

1261번: 알고스팟

단순하게 벽을 부수는 횟수를 카운트 하다가 오답이 계속 나왔는데 이를 해결하기 위해서 

새로 탐색하는 칸이 벽인 경우와 통로인 경우의 가중치를 다르게 주어야 한다. 

1) 통로 : 벽을 부수지 않아도 통과하여 이동할 수 있으므로 가중치가 높다. 덱 (deque) 의 앞쪽으로 밀어넣는다 

2) 벽 : 벽을 부수어야 하므로 가중치가 낮다. 덱 (deque) 의 뒤쪽으로 밀어넣는다 

 

# https://www.acmicpc.net/problem/1261
# 유형 : 0-1 너비 우선 탐색, 여기서 0-1 은 가중치를 의미한다. 

from collections import deque

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

board = [list(map(int, input())) for _ in range(N)]

queue = deque()
queue.append([0, 0]) # x, y

# 벽 부신 횟수 저장하기
distance = [[-1] * M for _ in range(N)]
distance[0][0] = 0
while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < M and distance[nx][ny] == -1:

            if board[nx][ny] == 0: # 통로 -> 가중치가 더 높으므로 appendleft
                distance[nx][ny] = distance[x][y]
                queue.appendleft([nx, ny])
            else: # 벽 -> 가중치가 낮으므로 append (right)
                distance[nx][ny] = distance[x][y] + 1
                queue.append([nx, ny])


print(distance[N-1][M-1])