BOJ 2206 - BFS

한번 벽을 부수는 것이 가능한 2차원배열 최단거리 찾기 문제이다. 같은 좌표에 재방문 하지 않도록 방문여부를 기록하는 평범한 bfs풀이로 접근했더니 문제가 발생하였다. 벽을 아직 부수지않은 (부술 수 있는 기회가 있는) 큐보다 먼저 벽을 부쉈던 큐가 방문여부를 기록해버려서 오답이 나오고 있었다.
해결방법은 부수고 이동하는 방문기록과 아직 부수지 않고 이동하는 방문기록을 개별로 기록하도록 하였다.

import collections

n,m = [*map(int, input().split(' '))]
board = []
for _ in range(n):
    board.append(input())

visited = set()
visited_after_break = set()
q = collections.deque([(0,0,1,False)])

while q:
    cur_y,cur_x,cost,used = q.popleft()
    if (cur_y,cur_x) == (n-1,m-1):
        print(cost)
        exit()
    for yy,xx in [(1,0),(0,1),(-1,0),(0,-1)]:
        nxt_y,nxt_x = cur_y + yy,cur_x + xx
        if nxt_y < 0 or nxt_y >= n:
            continue
        if nxt_x < 0 or nxt_x >= m:
            continue
        if board[nxt_y][nxt_x] == '1':
            if used == False:
                q.append((nxt_y,nxt_x,cost + 1,True))        
            continue
        if used == True and (nxt_y,nxt_x) not in visited_after_break:
            q.append((cur_y + yy,cur_x + xx, cost + 1, used))
            visited_after_break.add((nxt_y,nxt_x))
        elif used == False and (nxt_y,nxt_x) not in visited:
            q.append((cur_y + yy,cur_x + xx, cost + 1, used))
            visited.add((nxt_y,nxt_x))

print(-1)