풀이
처음에는 3차원배열로 방문처리를 받지 않고 주어진 2차원배열에서 값을 수정해주는 식으로 방문처리를 대체했고 큐에 들어가는 요소들에만 벽을 뚫을 수 있는지의 여부를 함께 삽입했다.
테스트 케이스에서는 모두 통과했지만 자꾸 틀린 답이 나왔다길래 다른분들의 코드를 참고했다.
아이디어는 같지만 내 코드와 다른점은 3차원 배열로 따로 방문처리를 해줬다는 것이다.
굳이 왜 저렇게 해야하는지 아직까지 의문이라 조금 더 공부해봐야겠다.
소스코드
# 벽 부수고 이동하기
from collections import deque
import sys
input = sys.stdin.readline
def bfs(i, j):
q = deque()
q.append([i, j, 1])
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
visited[i][j][1] = 1 # 시작 점 방문처리
while q:
x, y, penetrate = q.popleft()
if x == n-1 and y == m-1:
return visited[x][y][penetrate]
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < m: # 범위 내 일 때
if board[nx][ny] == 1 and penetrate == 1:
visited[nx][ny][0] = visited[x][y][1] + 1 # 방문 처리
q.append([nx, ny, 0])
elif board[nx][ny] == 0 and visited[nx][ny][penetrate] == 0:
visited[nx][ny][penetrate] = visited[x][y][penetrate] + 1 # 방문 처리
q.append([nx, ny, penetrate])
return -1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n, m = map(int, input().split())
board = [list(map(int, input().rstrip())) for _ in range(n)]
print(bfs(0, 0))