백준 2206 벽 부수고 이동하기

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

백준 문제집에서 SW역량테스트 준비 문제집을 풀고 있는데, 처음에는 어려웠지만 점점 익숙한 유형이 나오는 것 같다.

백준 1194번 문제를 풀었다면 같은 논리의 문제이다.
최단거리를 구하는 bfs 문제인데, 같은 칸에 다른 상태는 다르게 처리해주어야 한다는 논리이다.
위의 문제는 임의의 어느 위치에서 벽을 이전에 벽을 부수고 왔을 상태와 벽을 안부쉈을 상태를 나누어야 한다는 것이다.
배열의 크기도 1000 1000 2로 크기를 넘지 않는것을 고려하면 3차원 bfs를 구현하면 된다.

from collections import deque
n,m = map(int,input().split())
arr = []
for i in range(n):
    arr.append(list(map(int,input())))
q = deque([])
q.append((0,0,0))
dx = [-1,0,1,0]
dy = [0,1,0,-1]
visited = [[[-1]*2 for i in range(m)] for i in range(n)]
visited[0][0][0] = 0
while q:
    # print(q)
    x,y,cnt = q.popleft()
    if x == n-1 and y == m-1:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if arr[nx][ny] == 1:
            if cnt == 0 and visited[nx][ny][cnt+1] == -1:
                visited[nx][ny][cnt+1] = visited[x][y][cnt] + 1
                q.append((nx,ny,cnt+1))
        elif arr[nx][ny] == 0:
            if visited[nx][ny][cnt] == -1:
                visited[nx][ny][cnt] = visited[x][y][cnt] + 1
                q.append((nx,ny,cnt))
l = visited[n-1][m-1][0]
r = visited[n-1][m-1][1]
if l == -1 and r == -1:
    print(-1)
elif l == -1 or r == -1:
    print(max(l,r)+1)
else:
    print(min(l,r)+1)