[백준 2206] 벽 부수고 이동하기 (python)

2206번: 벽 부수고 이동하기

---

최단거리니깐 BFS로! 부수기 찬스 여부도 함께 저장해준다.

1. [찬스 없을때, 찬스 있을때]를 저장하는 visited 배열을 생성한다.
2. queue에는 [x좌표, y좌표, 찬스 여부, 경로]를 저장한다.
3. BFS 하기.

import sys
from collections import deque

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

input = sys.stdin.readline
N, M = map(int, input().split())
arr = []
visited = [[[0, 0] for _ in range(M)] for _ in range(N)]
for _ in range(N):
    arr.append(list(map(int, input().rstrip())))

queue = deque([[0, 0, 1, 1]])
visited[0][0] = [1, 1]
answer = -1

while queue:
    x, y, canBreak, cnt = queue.popleft()
    if x == N-1 and y == M-1:
        answer = cnt
        break
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny][canBreak]:
            if arr[nx][ny] == 1 and canBreak == 1:
                queue.append([nx, ny, 0, cnt+1])
                visited[nx][ny][canBreak] = 1
            elif arr[nx][ny] == 0:
                queue.append([nx, ny, canBreak, cnt+1])
                visited[nx][ny][canBreak] = 1

print(answer)