[0-1] BFS 시리즈

현재 위치가 [0,1]이냐를 볼 것이 아니고,
부수고 왔느냐, 아니냐에 대한 히스토리가 중요하다

즉 자신의 발자취를 큐에서부터 뽑을 수 있어야한다 (결국 큐에 담아야함)
[0] : 벽을 부수지 않고 현재의 위치에 도달한 경우.
[1] : 벽을 한 번 부수고 현재위치에 도달한 경우.

현재 큐에서 뽑은 것이 벽을 부수고 온 것이면
벡터가 벽일때는 continue(1번만 부술 수 있기 때문)
아닐때는 반드시 벡터의 [1]로.

현재 큐에서 뽑은 것이 벽을 부수지 않고 온 것이면,
벡터가 벽일때는 큐에 (dy,dx,1) ::: 1의 의미는 이제 부쉈다는 뜻. 대신 자신의 [0]에서[1]로 +1만큼 비용처리
벡터가 벽이 아닌 경우에는 [0]에서 [0]으로 +1 비용처리

---

코드

import sys
from collections import deque

n, m = map(int,sys.stdin.readline().strip().split())
origin = []
for ___ in range(n):
    origin.append(list(map(int, sys.stdin.readline().strip())))
check = [[[0,0] for _ in range(m)] for __ in range(n)]
###

def bfs():
    q = deque()
    q.appendleft((0,0,0)) #벽을 뚫었는지 여부
    check[0][0][0] = 1 #[1]에 대해서는 어떻게 할지 생각해볼것
    check[0][0][1] = 1
    ny = [0,0,1,-1]
    nx = [1,-1,0,0]
    while(q):
        y,x,b = q.pop()
        for i in range(4):
            dy = ny[i] + y
            dx = nx[i] + x
            if dy < 0 or dx < 0 or dy>=n or dx >=m:
                continue
            if b:
                if origin[dy][dx] or check[dy][dx][1]:
                    continue
                check[dy][dx][1] = check[y][x][1] + 1
                q.appendleft((dy,dx,1))
            else:
                if origin[dy][dx]:
                    if check[dy][dx][1]:
                        continue
                    check[dy][dx][1] = check[y][x][0] + 1
                    q.appendleft((dy,dx,1))
                else:
                    if check[dy][dx][0]:
                        continue
                    check[dy][dx][0] = check[y][x][0] + 1
                    q.appendleft((dy,dx,0))
bfs()
mmin = 100000000
if check[n-1][m-1][0] and check[n-1][m-1][0] < mmin:
    mmin = check[n-1][m-1][0]
if check[n-1][m-1][1] and check[n-1][m-1][1] < mmin:
    mmin = check[n-1][m-1][1]
if mmin == 100000000:
    print(-1)
else:
    print(mmin)

---

14442(벽 부수고 이동하기2)

동일한 원리임.

벡터가 벽이 아니면
자신의 히스토리를 그대로 따라가면 된다.

벡터가 벽이라면
자신의 히스토리에서 하나를 더 추가해준다 [b]에서 [b+1]로 +1만큼 비용처리
*예외처리 : b==k일때는 continue 추가

코드

import sys
from collections import deque

n, m, k = map(int,sys.stdin.readline().strip().split())
origin = []
for ___ in range(n):
    origin.append(list(map(int, sys.stdin.readline().strip())))
check = [[[0]*(k+1) for _ in range(m)] for __ in range(n)]
for p in range(k+1):
    check[0][0][p] = 1
def bfs():
    q = deque()
    q.appendleft((0,0,0))
    ny = [0,0,1,-1]
    nx = [1,-1,0,0]
    while(q):
        y,x,b = q.pop()
        for i in range(4):
            dy = ny[i] + y
            dx = nx[i] + x
            if dy < 0 or dx < 0 or dy>=n or dx >=m:
                continue
            if origin[dy][dx] == 0: #vec!=wall
                if check[dy][dx][b]:
                    continue
                check[dy][dx][b] = check[y][x][b] + 1
                q.appendleft((dy,dx,b))
            else:#vector가 벽인 경우
                if b==k or check[dy][dx][b+1]:
                    continue
                check[dy][dx][b+1] = check[y][x][b] + 1
                q.appendleft((dy,dx,b+1))
bfs()
mmin = 100000000
for j in range(k+1):
    if check[n-1][m-1][j] and check[n-1][m-1][j] < mmin:
        mmin = check[n-1][m-1][j]

if mmin == 100000000:
    print(-1)
else:
    print(mmin)