이번 문제는 전에 풀었던 문제와 매우 유사하였다. 물의 좌표를 큐에 담고, 4방향으로 물을 퍼트리며 새로운 좌표를 새로운 큐에 넣은 후, 새로운 좌표들이 담긴 큐를 물의 좌표 큐로 복사시킨다. 이렇게 하면 불필요한 물의 좌표 탐색을 줄일 수 있다. 그리고 고슴도치의 이동을 하며, 고슴도치의 이동한 시간과 현재 시간을 비교하여 현재 시간이 작거나 같을 경우에만 물을 퍼트린다. 고슴도치는 .과 D로만 이동이 가능하도록 구현하였고, popleft()를 한 직후에 grid[y][x]가 D일 경우에 고슴도치의 이동 시간을 반환하도록 하였다. while문이 종료되어도 반환값이 없을 경우에는 KAKTUS를 반환하도록 하였다.

Code

from collections import deque
from copy import copy
r, c=map(int, input().split())
grid=[list(str(input())) for _ in range(r)]
water=deque()
start=[]
for i in range(r):
    for j in range(c):
        if grid[i][j]=='*':
            water.append((i, j))
        if grid[i][j]=='S':
            start=[i, j]
            grid[i][j]='.'
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
def water_spread():
    global water
    water_q=deque()
    while water:
        y, x=water.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<r and 0<=nx<c and grid[ny][nx]=='.':
                water_q.append((ny, nx))
                grid[ny][nx]='*'
    water=copy(water_q)
def s_move(y, x):
    q=deque()
    q.append((y, x, 0))
    visited=[[False for _ in range(c)] for _ in range(r)]
    visited[y][x]=True
    time=0
    while q:
        y, x, cnt=q.popleft()
        if grid[y][x]=='D':
            return cnt
        if time<=cnt:
            water_spread()
            time+=1
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<r and 0<=nx<c and not visited[ny][nx] and grid[ny][nx] in [".", "D"]:
                q.append((ny, nx, cnt+1))
                visited[ny][nx]=True
    return 'KAKTUS'
print(s_move(start[0], start[1]))