BOJ 3055 탈출(Python 3)

https://www.acmicpc.net/problem/3055

BFS를 두번 돌리는 문제이다.

이전에 화산쇄설류와 같은 유형의 문제이다.

물의 이동을 먼저 BFS로 돌리고, 그다음 민혁이의 이동을 BFS로 돌린다.

이때, 민혁이가 어떤 좌표 x에 가려고 한다면 물이 x에 도착하는 시간보다 빨라야 이동할 수 있다.

해당 부분만 유의하면 충분히 맞을 수 있는 문제이다.

코드확인

from collections import deque
r,c=map(int,input().split())
S=[input() for _ in range(r)]
dx,dy=[0,0,1,-1],[1,-1,0,0]
water_D=[[-1]*c for _ in range(r)]
D=[[-1]*c for _ in range(r)]
q=deque()
for i in range(r):
    for j in range(c):
        if S[i][j]=='*':
            q.append((i,j))
            water_D[i][j]=0
        elif S[i][j]=='S':
            sx,sy=i,j
        elif S[i][j]=='D':
            ex,ey=i,j
while q:
    x,y=q.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<r and 0<=ny<c and S[nx][ny] not in 'DX' and water_D[nx][ny]==-1:
            water_D[nx][ny]=water_D[x][y]+1
            q.append((nx,ny))
q.append((sx,sy))
D[sx][sy]=0
while q:
    x,y=q.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<r and 0<=ny<c and D[nx][ny]==-1 and S[nx][ny] not in '*X':
            if water_D[nx][ny]==-1 or D[x][y]+1<water_D[nx][ny]:
                D[nx][ny]=D[x][y]+1
                q.append((nx,ny))
print([D[ex][ey],'KAKTUS'][D[ex][ey]==-1])