물이 차있는 지역이 없을 수 도있고 여러개인 경우를 고려하지 못해서 처음엔 런타임에러가 떴다.
도착점을 제외하고는 고슴도치는 물이 찰 예정인 칸으로 갈 수 없으므로 목표좌표에 고슴도치부터 이동시키고 물과 고슴도치가 만난다면 물로 표시했다
from collections import deque
N,M = map(int,input().split())
arr = [list(input()) for _ in range(N)]
used = [[0] * M for _ in range(N)] # 물의 방문체크
used2 = [[0] * M for _ in range(N)] # 고슴도치의 방문체크
directy = [-1,1,0,0]
directx = [0,0,-1,1]
q = deque()
tmp1,tmp2 = [],[]
result,flag = 0,0
for j in range(N):
for i in range(M):
if arr[j][i] == 'S':
tmp1 = [j,i,'S'] # 고슴도치의 위치
arr[j][i] = 0
used2[j][i] = 1
if arr[j][i] == '*': # 물이 있는 좌표를 tmp2에 저장
tmp2.append([j,i,'*'])
used[j][i] = 1
flag += 1
if arr[j][i] == 'D':
used[j][i] = 1 # 도착점에는 물이 도착할 수 없도록 used에 방문체크
q.append(tmp1) # 고슴도치부터 q에 추가
for i in range(flag):
q.append(tmp2[i])
def bfs():
global result,q
while q:
y,x,s = q.popleft()
# for i in range(N):
# print(*arr[i])
# print(result, q)
for k in range(4):
dy = directy[k] + y
dx = directx[k] + x
if dy >= N or dy < 0 or dx >= M or dx < 0 or arr[dy][dx] == 'X': # 배열을 벗어나거나 벽이라면 continue
continue
if s == 'S': # 고슴도치
if arr[dy][dx] == 'D' and used[y][x] == 0: # 목적지에 도착했다면 result에 이동거리 저장
result = arr[y][x] + 1
q = []
break
if used2[dy][dx] == 0 and used[dy][dx] == 0 and used[y][x] == 0: # 고슴도치가 방문하지 않았고, 목표지점과 현재위치가 물이 없다면 이동
used2[dy][dx] = 1
arr[dy][dx] = arr[y][x] + 1
q.append([dy,dx,'S'])
if s == '*': # 물
if used[dy][dx] == 0: # 방문안한곳 방문
used[dy][dx] = 1
arr[dy][dx] = '*'
q.append([dy,dx,'*'])
bfs()
if result == 0: # 도착하지못하면 KAKTUS 출력
print("KAKTUS")
else:
print(result)
