길과 벽으로 이루어진 N x M크기의 공간이 있고 (1, 1)에서 시작해서 (N, M)까지 가는 최단거리를 구하는 문제이다.
단, 벽을 한 번 부술 수 있는 기회가 있다.
처음에는 나름대로 줄여보겠다고 부쉈을 때 의미가 있는 ? 그러니까 새로운 길로 나아갈 수 있는 길을 찾아 부수고 bfs를 했다. 이렇게 모든 경우를 다 해봤을 때 가장 짧은 길을 구했더니 당연하게도 시간초과가 났다. 이렇게 단순할리가 없지.
한참을 고민해도 아이디어를 떠올리지 못해서 약간의 검색을 통해 3차원 배열을 사용한다는 것과 벽을 부순 경우와 부수지 않은 경우로 나누어 생각해야한다는 아이디어를 얻었다.
아이디어를 얻고도 한참을 씨름한 끝에 해결해냈다.
나는 큐에 [ (좌표), 이동거리, 벽 뚫은 여부 ] 를 한 세트로 담았다.
그리고 경우를 나누어
1. 벽을 뚫은 적이 없다
1-1. 새로 나아갈 곳이 벽도 아니고 방문한 적도 없다
1-2. 새로 나아갈 곳이 벽인데 아직 뚫은 적이 없는 벽이다
2. 벽을 뚫은 적이 있다
2-1. 새로 나아갈 곳이 벽도 아니고 방문한 적도 없다
2-2. 새로 나아갈 곳이 벽이다
이렇게 나누었는데, 2-2는 사실 체크할 필요가 없다. 이미 벽을 뚫었기 때문에..
이렇게 나누고 아직 벽을 뚫지 않고 나아가고 있는 경우라면 3차원의 visited 중 1층(?) 부분에 기록을 하고
벽을 뚫은 경우라면 2층 부분에 기록을 했다. ( N x M 짜리 visted가 2층으로 이루어진 3차원 배열)
만약 1층에서 탐색을 하다가 벽을 만나면 같은 자리 2층으로 올라가서 계속 탐색을 이어나간다고 생각하면 될 것 같다.
이렇게 했을 때 처음에 걱정했던 것이
- 벽을 뚫고 간 곳이 만약 이미 탐색한 곳이면?
- 벽을 뚫고나서 끝지점에 도착해서 끝냈는데 만약 그것보다 더 짧은 길이 있다면?
이런 내용들이었는데 생각해보면,
1번 걱정은 이미 탐색을 한 곳이라면, 그 길을 통해 가봤자 막혔거나, 지나온 길일 것이라는 것
2번 걱정은 bfs 자체가 최단 경로를 찾는 것이라 쓸데 없는 고민이라는 것
나름대로 이렇게 결론을 내렸다.
그리고 1 x 1 짜리 공간일 경우의 예외처리가 필요했다.
아래 예제가 문제 해결에 많이 도움이 되었다.
'''
13 13
0100011011000
0001001010000
0000100001000
1100010101011
1111101111000
1011010001001
0100001001001
0100111010001
0101010000100
0001110100000
0000001000100
1010001000111
1001000100000
27
'''from sys import stdin, version_info
from collections import deque
from typing import AnyStr
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def bfs():
visited = [[[0 for i in range(m)] for j in range(n)] for k in range(2)]
q = deque()
q.append([(0,0), 1, False])
visited[0][0][0] = 1
while q:
now = q.popleft()
if now[0][0]==n-1 and now[0][1]==m-1:
return 1
for i in range(4):
nx = now[0][0] + dx[i]
ny = now[0][1] + dy[i]
if 0<=nx<n and 0<=ny<m:
if now[2] == False: #벽을 뚫은 적이 없다
if g[nx][ny] == 0 and visited[0][nx][ny] == 0: #벽도 아니고 방문한적 없다
q.append([(nx, ny), now[1]+1, False])
visited[0][nx][ny] = now[1]+1
if nx==n-1 and ny==m-1:
return visited[0][nx][ny]
elif g[nx][ny] == 1 and visited[1][nx][ny] == 0 and visited[0][nx][ny] == 0: #벽이고 뚫은 적이 없다
q.append([(nx, ny), now[1]+1, True]) #뚫기
visited[1][nx][ny] = now[1]+1
else: #뚫은 적이 있다
if g[nx][ny] == 0 and visited[1][nx][ny] == 0 and visited[0][nx][ny] == 0: #길이고 방문한 적이 없다
q.append([(nx, ny), now[1]+1, True])
visited[1][nx][ny] = now[1]+1
if nx==n-1 and ny==m-1:
return visited[1][nx][ny]
return -1
n,m = map(int, stdin.readline().split())
g = [list(map(int, list(stdin.readline().rstrip()))) for i in range(n)]
print(bfs())