이번 문제는 BFS를 통해 해결하였다. 처음에는 문제를 보자마자 벽을 없애는 모든 경우에 대하여 bfs 함수를 돌리는 것으로 생각하고 구현을 하였다. 그러나 N과 M의 범위가 커서 시간 복잡도가 터져 시간 초과가 발생하였다. 그래서 이번에는 bfs 함수 내에서 magic이라는 변수를 사용하여 벽을 만났을 때 magic이 1일 경우 벽을 제거하고 그 자리로 이동하도록 구현하였다. 그런데 이번에는 3%에서 오답 처리 되었고, 벽을 뿌시지 않아도 되는 경우에는 뿌시지 않아야 하는 반례가 존재한다는 사실을 알게 되었다.

그래서 bfs 함수 내의 방문 처리 리스트를 3차원으로 구현하여 벽을 뿌시고 간 경우와 뿌시지 않은 경우에 대하여 방문처리를 진행하였고, 이를 사용하여 정답 처리 받을 수 있었다.

Code

import collections
n, m=map(int, input().split())
hy, hx=map(int, input().split())
ey, ex=map(int, input().split())
hy, hx, ey, ex=hy-1, hx-1, ey-1, ex-1
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
def bfs(y, x):
    q=collections.deque()
    q.append((y, x, 0, 1))
    visited=[[[False for _ in range(2)] for _ in range(m)] for _ in range(n)]
    visited[y][x][1]=True
    while q:
        y, x, cnt, magic=q.popleft()
        if (y, x)==(ey, ex):
            return cnt
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m:
                if visited[ny][nx][magic]:
                    continue
                if grid[ny][nx]==1 and magic==1:
                    visited[ny][nx][0]=True
                    q.append((ny, nx, cnt+1, magic-1))
                elif grid[ny][nx]==0:
                    visited[ny][nx][magic]=True
                    q.append((ny, nx, cnt+1, magic))
    return -1
print(bfs(hy, hx))