import sys
from collections import deque
input = sys.stdin.readline
def bfs():
global INF,result
stack = deque()
stack.append((0,0,1,0))
visited = [[[INF for z in range(2)] for _ in range(M)] for _ in range(N)]
visited[0][0][0] = 1
visited[0][0][1] = 1
while stack:
x,y,dis,wall_cnt = stack.popleft()
if x== N-1 and y == M-1:
if result > dis:
result = dis
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx< N and 0<= ny < M:
if visited[nx][ny][wall_cnt] > dis + 1 and wall_cnt <=1:
if arr[nx][ny] == '1' and not wall_cnt:
visited[nx][ny][wall_cnt] = dis + 1
stack.append((nx,ny,dis+1,wall_cnt+1))
elif arr[nx][ny] == '0':
visited[nx][ny][wall_cnt] = dis +1
stack.append((nx,ny,dis+1,wall_cnt))
N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(input()) for _ in range(N)]
wall = []
INF = float('inf')
result = INF
bfs()
if result == INF:
print(-1)
else:
print(result)처음 풀었던 방식은 BFS를 하면서 방문을 했는지 안했는지를 하나의 축으로 추가해서 visited에 표시를 해주는 거였다.
import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
arr = [list(input()) for _ in range(N)]
INF = float('inf')
distance_front = [[INF]*M for _ in range(N)]
distance_back = [[INF]*M for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
stack1 = deque()
stack2 = deque()
distance_front[0][0] = 1
distance_back[N-1][M-1] = 0
stack1.append((0,0))
stack2.append((N-1,M-1))
while stack1:
x,y = stack1.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx <N and 0<= ny <M:
if distance_front[nx][ny] == INF:
distance_front[nx][ny] = distance_front[x][y] +1
if arr[nx][ny] == '0':
stack1.append((nx,ny))
while stack2:
x,y = stack2.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx <N and 0<=ny <M:
if distance_back[nx][ny] == INF:
distance_back[nx][ny] = distance_back[x][y] + 1
if arr[nx][ny] == '0':
stack2.append((nx,ny))
result = distance_front[N-1][M-1]
for x in range(N):
for y in range(M):
if arr[x][y] == '1':
result = min(result,distance_front[x][y]+distance_back[x][y])
if result != INF:
print(result)
else:
print(-1)개선된 방식은 0,0에서 BFS를 돌리고, 목표지점인 (N-1,M-1)에서 BFS를 돌린다. 그리고 BFS를 돌리면서 최단거리를 저장해놓는다.
그리고 첫번째 돌린 BFS의 최단거리에서 목표지점까지의 최단거리를 구하고,
벽을 부셨을때 최단거리는 두개의 BFS의 합을 통해 구한다.
벽인 지점 (A,B)가 있으면, 첫번째 돌린 BFS의 (A,B)의 값과 두번째 돌린 BFS의 (A,B)을 합쳐주면 그 벽을 부셨을때의 최단 이동거리가 된다.
위와 같이 할려면 초기값을 주의해야하는데, 첫번째 BFS의 초기값은 1이고, 두번째 BFS는 0이다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 1520 내리막길 (0) | 2021.03.04 |
|---|---|
| [BOJ/백준] 2580 스도쿠 (0) | 2021.03.02 |
| [BOJ/백준] 11000 강의실 배정 (0) | 2021.02.27 |
| [BOJ/백준] 13911 집구하기 (0) | 2021.02.27 |
| [BOJ/백준] 2467 용액 (0) | 2021.02.27 |