[백준][파이썬] 2206 벽 부수고 이동하기 - 메모리초과

BFS문제이지만 기존의 문제들과는 조금의 차이가 있다.

벽을 뚫을수 있다는 것을 체크해줘야한다.

1. 벽 뚫기를 위해 [x,y, 횟수] 이런식으로 저장을 해준다.

2. visited를 활용할때 주의할 점은 벽 안뚫기 / 벽 뚫었을때 따로 방문여부를 체크해줘야한다

(만약에 체크해주지 않으면, 벽뚫 vs 안뚫 이 만났을 때 오류가 생긴다

 

3. 메모리초과를 해결하지 못했다.....

import sys
import collections
n, m = map(int,sys.stdin.readline().split())
map1 = [list(map(int,[*input()])) for k in range(n)]

def recu(stack):
    stack.append([0,0,0])
    cnt = 1
    while stack:
        cnt += 1
        for w in range(len(stack)):
            x = stack[0][0]
            y = stack[0][1]
            check = stack[0][2]
            stack.popleft()
            for i in range(4):
                X = x+dx[i]
                Y = y+dy[i]
                if 0<= X < n and 0<=Y<m and map1[X][Y] == 1 and visited[X][Y][1] == -1 and check == 0:
                    visited[X][Y][1] = cnt
                    stack.append([X,Y,1])
                elif 0<= X < n and 0<=Y<m and map1[X][Y] == 0 and visited[X][Y][0] == -1:
                    visited[X][Y][check] = cnt
                    stack.append([X,Y,check])
                    if X == n-1 and Y == m-1:
                        print(cnt)
                        return
    print(-1)
    return
visited = [[[-1,-1] for i in range(m)] for j in range(n)]
dx = [0,0,-1,1]
dy = [1,-1,0,0]
st = collections.deque()
recu(st)