[백준] 2206번 벽 부수고 이동하기 파이썬 코드

백준

# 벽을 부쉈는지, 부수지 않았는지에 대한 방문기록이 나뉜다

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int, input().split())
graph = [input() for _ in range(n)]
visited = [[[0]*2 for _ in range(m)] for _ in range(n)] # 3차원 배열
dx, dy = (1,-1,0,0), (0,0,1,-1) # 이동 경로
def bfs():
  queue = deque([(0,0,0)])
  visited[0][0][0] = 1 # 출발장소 방문체크
  while queue:
    popx, popy, bukbbu = queue.popleft()
    if popx == n-1 and popy == m-1: return visited[popx][popy][bukbbu]
    for i in range(4):
      nx = popx+dx[i]
      ny = popy+dy[i]
      if 0<=nx<n and 0<=ny<m:
        if graph[nx][ny] == '0' and not visited[nx][ny][bukbbu]: 
          visited[nx][ny][bukbbu] = visited[popx][popy][bukbbu]+1
          queue.append((nx,ny,bukbbu))
        elif graph[nx][ny]=='1' and not bukbbu: # 벽을 부수지 않은 경우
          visited[nx][ny][1] = visited[popx][popy][0]+1 # 방문체크하는 리스트 전환
          queue.append((nx,ny,1))
  return -1 # 도달하지 못하면 -1 반환
print(bfs())

벽을 부수는 경우까지는 캐치했는데, 방문기록에서 막힌 문제이다. 변수 3개 둘 생각은 했으면서  3차원 배열을 만들지 못한 내가 신기하다. 0-1 bfs로 풀릴 줄 알고 달려들었다가 꽤 애먹은 문제였다.