백준 3055번 탈출 파이썬

[문제 링크]

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

[입출력 예]

입력	출력
3 3 D.* ... .S.	3

[소스코드]

import sys
from collections import deque
input = sys.stdin.readline

dx=[1,0,-1,0]
dy=[0,1,0,-1]

r, c = list(map(int,input().split()))

board1 = []
Dx, Dy , Sx,Sy=0,0,0,0
water=deque()

for i in range(r):
    tmp=list(input().rstrip())
    for j in range(c):
        if tmp[j]=='D':
            Dx =i
            Dy =j
        if tmp[j]=='S':
            Sx = i
            Sy = j
        if tmp[j]=='*':
            water.append((i,j))
    board1.append(tmp)

board2 = [item[:] for item in board1]

for waterPos in water:
    board1[waterPos[0]][waterPos[1]]=0



while (water):

    x,y = water.popleft()
    for i in range(4):
        nx = x +dx[i]
        ny = y +dy[i]

        if ( nx<0 or nx >=r or ny < 0 or ny >=c): continue
        if ( board1[nx][ny]=='D' or board1[nx][ny]=='X' or str(board1[nx][ny]).isdigit()): continue

        board1[nx][ny]=board1[x][y]+1

        water.append((nx,ny))


board2[Sx][Sy]=0

hog = deque()
hog.append((Sx,Sy))


while(hog):
    x,y= hog.popleft()
    for i in range(4):
        nx= x+ dx[i]
        ny= y+ dy[i]

        if ( nx<0 or nx >=r or ny < 0 or ny >=c): continue
        if (board2[nx][ny]=='X' or str(board2[nx][ny]).isdigit() or (str(board1[nx][ny]).isdigit()and board1[nx][ny]<=board2[x][y]+1) ): continue

        board2[nx][ny]=board2[x][y]+1
        if (board1[nx][ny]=='D') : break


        hog.append((nx,ny))


if (board2[Dx][Dy]=='D') :print('KAKTUS')
else : print(board2[Dx][Dy])