import sys
input = sys.stdin.readline
from collections import *
dy = [1,-1,0,0]; dx = [0,0,1,-1]
def BFS():
dq = deque()
for i in range(4):
y1,x1 = ys+dy[i],xs+dx[i]
if N>y1>=0 and M>x1>=0 and not board[y1][x1]:
dq.append((y1,x1,1,i,1))
visited = [[0]*M for i in range(N)]
direction = [[[0]*4 for i in range(M)] for i in range(N)]
while dq:
y,x,cnt,d,k = dq.popleft()
if y==ye and x==xe:
return cnt
if visited[y][x] and visited[y][x]<cnt:
continue
if visited[y][x] == cnt:
if direction[y][x][d]>=k:
continue
else:
direction[y][x] = [0]*4
visited[y][x] = cnt
direction[y][x][d] = k
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and not board[y1][x1]:
if i==d and k<K:
dq.appendleft((y1,x1,cnt,i,k+1))
else:
dq.append((y1,x1,cnt+1,i,1))
return -1
N,M,K = map(int,input().split())
board = [[*map(lambda x:1 if x=="#" else 0,input().strip())] for i in range(N)]
ys,xs,ye,xe = map(lambda x:int(x)-1,input().split())
print(BFS())BFS 응용문제
0-1 BFS와 방향에 대한 visited를 이용하여 해결하였다.
이전에 전구를 켜라 [백준 2423번] 전구를 켜라 (Python3) (tistory.com) 문제를 풀면서 deque에 거리가 0이면 appendleft, 거리가 1이면 append를 하는 방식으로 문제를 해결한 적이 있었고, 나중에 알고보니 이런 풀이가 0-1 BFS였다.
또, 레이저 통신 [백준 6087번] 레이저 통신 (Python3) (tistory.com) 문제를 풀면서 visited 배열에 방향에 대한 요소를 추가하고, cnt가 같은 경우 방향이 포함되어있지 않은 경우에만 continue하는 방식으로 문제를 해결하였었다.
이번 문제는 이 두 아이디어를 합쳐서 해결할 수 있었다.
풀이를 설명하면,
1. N*M 크기의 visited 배열을 만들고, visited 배열에는 cnt (소요시간) 을 기록한다.
2. N*M*4 크기의 direction 배열을 만들고, directions 배열에는 해당방향 이동횟수 k를 기록한다.
3. deque의 튜플에는 y좌표, x좌표, 소요시간, 이동방향, 해당방향 이동횟수 를 저장한다.
4. 같은 방향으로 이동하는 경우, 해당방향 이동횟수가 K보다 작은 경우 cnt는 그대로, k만 +1 해서 appendleft를 해준다.
5. 같은 방향으로 이동하는데 이동횟수가 K이거나, 다른 방향으로 이동하는 경우 cnt에 +1, k = 1로 append 해준다.
6. 이미 방문한 좌표에 도착시, 현재 cnt보다 작으면 continue, 크면 갱신해주고, 같은 경우에는 해당방향으로 이동한 기록이 있고 그때의 남은 이동횟수가 현재의 k보다 크거나 같으면 continue한다.
7. 목적지에 도착하면 cnt를 출력한다.
실수할 여지가 많은 문제라고 생각했는데, 의외로 한번에 통과되었다. 다양한 BFS 문제를 풀어본 경험이 도움이 된 것 같다.
오늘의 교훈) 다양한 문제를 풀며 얻은 데이터를 잘 활용하자