문제 링크
https://www.acmicpc.net/problem/2206
잡담
벽은 왜 부수고 그러실까
구현
처음에 BFS를 그냥 냅다 박아버리면 18%에서 틀린다. 이에 대해 질문 게시판에 좋은 반례가 하나 있다.
6 5
00000
11110
00000
01111
01111
00010
위 반례를 실행해보면, (2, 1)의 벽을 부수고 내려온 visited 때문에 원래 가야할 길이 막히는 것을 알 수 있다. 살짝 질문 게시판을 참고했는데, visited와 broker (벽을 부순) visited를 따로 체크해주면 된다고 했다.
나는 벽을 부순 친구는 2로 배열에 체크하고, 아직 부수지 않은 친구는 -1로 체크하여 구분하였다.
코드
from sys import stdin
from collections import deque
input = lambda : stdin.readline().strip()
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
queue = deque()
queue.append(((0, 0), 1, False))
graph[0][0] = -1
while queue:
node = queue.popleft()
if node[0] == (m - 1, n - 1):
break
for i, j in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
new_x, new_y = node[0][0] + i, node[0][1] + j
if 0 <= new_x < m and 0 <= new_y < n:
if node[2]:
if graph[new_y][new_x] == 0:
queue.append(((new_x, new_y), node[1] + 1, node[2]))
graph[new_y][new_x] = 2
else:
if graph[new_y][new_x] >= 0:
if graph[new_y][new_x] == 1:
queue.append(((new_x, new_y), node[1] + 1, True))
else:
queue.append(((new_x, new_y), node[1] + 1, node[2]))
graph[new_y][new_x] = -1
if node[0] == (m - 1, n - 1):
print(node[1])
else:
print(-1)