문제
접근
조금 까다로웠던 것 같다.
BFS로 푸는 건 맞는 것 같은데, 벽을 최대 한개까지는 부술 수 있다.
이걸 어떻게 처리해줄지 고민했던 문제이다.
생각보다 단순하게 풀 수 있었는데, 기존에는 벽이 아닌 경우에만 queue에 좌표를 추가해주었다.
여기서는 queue에 현재 좌표와 벽을 부쉈는지를 저장해두고,
벽을 부수지 않았으면 벽인 경우도 한 번은 이동할 수 있도록 처리해주었다.
이 때 방문배열을 벽을 부순적이 없는 경우, 벽을 부순 경우 두개로 사용해주어야 한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import deque
def bfs():
dx = [0,0,1,-1]
dy = [1,-1,0,0]
q = deque()
q.append((0,0,0))
visit[0][0][0] = 1
while q:
nowx, nowy, cnt = q.popleft()
if nowx == w-1 and nowy == h-1:
return visit[nowy][nowx][cnt]
for x,y in zip(dx,dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= w or ny < 0 or ny >= h:
continue
if board[ny][nx] == 1 and cnt == 0:
visit[ny][nx][1] = visit[nowy][nowx][0] + 1
q.append((nx,ny,cnt+1))
elif board[ny][nx] == 0 and visit[ny][nx][cnt] == 0:
visit[ny][nx][cnt] = visit[nowy][nowx][cnt] + 1
q.append((nx,ny,cnt))
return -1
h, w = map(int, input().split(' '))
board = []
visit = [[[0] * 2 for _ in range(w)] for _ in range(h)]
for _ in range(h):
board.append([int(item) for item in input()])
ans = bfs()
print(ans)