백준 / 2206 / 벽 부수고 이동하기 (bfs)

시간 초과뜬 처음 시도 코드

import sys
from collections import deque
input = sys.stdin.readline
direction = [[1,0],[-1,0],[0,1],[0,-1]]

n, m = [int(v) for v in input().split()]
maps = [[0]*m for _ in range(n)]

for i in range(n):
    maps[i] = list(map(int, input().rstrip()))

q = deque([[0,0,1]])
result = 10e9
flag = False
tmp_check_list = [[False]*m for _ in range(n)]

while q:
    x, y, deph = q.popleft()
    if x == n-1 and y == m-1:
        min(result, deph+1)
        flag = True
        break
    
    maps[x][y] = 1
    for d in direction:
        nx, ny = x+d[0], y+d[1]
  
        if 0<= nx < n and 0 <= ny < m:
            if not tmp_check_list[nx][ny] and maps[nx][ny] == 1:
                tmp_check_list[nx][ny] = True
                tmp_maps = [arr[:] for arr in maps]
                tmp_maps[nx][ny] = 0
                tmp_q = deque([arr[:] for arr in list(q)[:]]) if q else deque([(x,y,deph)])
                while tmp_q:
                    t_x, t_y, t_deph = tmp_q.popleft()
                    if t_x == n-1 and t_y == m-1:
                        result = min(result, t_deph+1)
                        flag = True
                        break
                    tmp_maps[t_x][t_y] = 1
                    for d in direction:
                        t_nx, t_ny = t_x+d[0], t_y+d[1]
                        if 0<= t_nx < n and 0 <= t_ny < m and not tmp_maps[t_nx][t_ny]:
                            tmp_maps[t_nx][t_ny] = 1
                            tmp_q.append([t_nx, t_ny, t_deph+1])
            elif maps[nx][ny] == 0:
                maps[nx][ny] = 1
                q.append([nx,ny, deph+1])

if flag:        
    print(result-1)
else:
    print(-1)

bfs를 진행하면서 1 즉 벽을 만나면 현재 진행 상황을 복사한 후 해당 1을 0으로 바꿔서 진행해 보는 방식

예제 입력에 대해서 답이 맞긴 했지만 코드도 복잡할 뿐더라 시간 초과가 당연해 보인 듯 하다....

import sys
from collections import deque
input = sys.stdin.readline
direction = [[1,0],[-1,0],[0,1],[0,-1]]

n, m = [int(v) for v in input().split()]
maps = [[0]*m for _ in range(n)]
visited = [[[0]*2 for _ in range(m)] for _ in range(n)]

for i in range(n):
    maps[i] = list(map(int, input().rstrip()))

q = deque([[0,0,0,0]])
while q:
    x,y,z, deph = q.popleft()
    visited[x][y][z] = 1
    if x == n-1 and y == m-1:
        print(deph+1)
        break

    for d in direction:
        nx, ny = x+d[0], y+d[1]
        if 0 <= nx < n and 0 <= ny < m:
            if maps[nx][ny] == 1 and z == 0 and not visited[nx][ny][z+1]:
                visited[nx][ny][z+1] = 1
                q.append([nx, ny, z+1, deph+1])
            elif maps[nx][ny] == 0 and not visited[nx][ny][z]:
                visited[nx][ny][z] = 1
                q.append([nx,ny,z, deph+1])
else:
    print(-1)

3차원을 활용한 bfs
visited를 3차원으로 설정하여 벽을 부시고 진행했을 때와 아닌 경우를 구분해서 bfs 진행하는 방식으로 해결

bfs를 진행하다가 벽을 부신적이 없는 경우에서 벽을 만나면 z 값을 1로 해서 bfs 진행 1로 진행하면 다시 벽을 만날 때 진행 할 수 없다.